NP

Question 1

How to show a problem is in NP

Answer 1

Algorithm must be provided that can verify proposed solution (S) given an instance (I) efficiently in polynomial time relative to the size of I.

Question 2

[SAT]
Input

Answer 2

Boolean formula in CNF with n variables and m clause

Question 3

[SAT]
Output

Answer 3

Satisfying assignment or NO

Question 4

[SAT]

NP Proof - Show that SAT is in NP

Given f & assignment x1 … xn:

Answer 4

O(n) time to check that a clause is satisfied for m clauses.
O(nm) total time to verify.

Question 5

[3SAT]

NP Proof - Show that 3SAT is in NP

Given f & assignment x1 … xn:

Answer 5

Check a clause is satisfied O(1) (bc size of clauses is bounded by a constant)
m clauses, so O(m) and polynomial

Question 6

[Colorings]

Show that k-colorings is in NP

Answer 6

Given a k-coloring, check each edge to ensure endpoints have different colors, O(n+m)

Question 7

[MST]

Proof that MST is in NP

Answer 7

We can verify solution in poly-time by 2 checks:

• T is a tree: Run BFS to check connectivity, O(n+m)
• T is minimum weight: Compare MST with a Kruskal’s output, O(m log n)

Question 8

[MST]

How to prove MST is in P

Answer 8

Prove can solve in poly-time by running Kruskals

Question 9

[Knapsack, original]

How to verify solution S

Answer 9

sum of weight <= B & sum of value is maximum

Question 10

[Knapsack]

Why is knapsack not known to be in NP?

Answer 10

No poly-time method exists to verify value sum is maximal.
DP approach takes O(nB) time which is exponential relative to input size.

Question 11

[Knapsack search]

Difference from original knapsack

Answer 11

Instead of max value sum, verify that subset S exists with at least goal value g and at most weight W

Question 12

[Knapsack search vs optimization]

How to prove goal value

Answer 12

Binary search on g within the sum of all values (V), with the number of binary search rounds capped by log V. Takes O(log V)

Question 13

T/F

If the knapsack search version is solvable in polynomial time, so is the original optimization problem.

Answer 13

True

Why: if we can reduce KS to KS search then we show KS search is at least as hard as KS

How to reduce:
1. Compute an upper bound V on the maximum possible value (V = sum of all item values).
2. Perform binary search on g in the range [0, V] to find the maximum value for which the search version returns a solution.
3. For each iteration of binary search, we run the polynomial-time Knapsack-search

Question 14

[NP]

Significance of P != NP

Answer 14

There are problems that exist outside the class P (solvable in polynomial time), which are termed intractable or NP-complete

Question 15

[NP]

Contrapositive of “If P != NP, then all NP-complete problems are not in P”

Answer 15

“If a NP-complete problem can be solved in poly-time, then all problems in NP can be solved in poly-time”

Question 16

T/F

SAT is not in P

Answer 16

True. Considered most difficult problem in NP.

Question 17

[Reduction]

A -> B in words

Answer 17

If A has a solution then B has a solution

Question 18

[Reduction]

Key components for a reduction

Answer 18

Verify unknown problem is at least as hard as a known NP-C problem.
1. Input transformation is polynomial in time
2. Output transformation is polynomial in time
3. Bidrectional proof of correctness, ie. if known NP-C problem solution is correct, then unknown problem is correct. If NP-C S not correct, then unknown problem S not correct.

Question 19

[Reduction]
How to prove NP-Completeness

Answer 19

1. Verify in poly-time
2. Use an existing NP-Complete problem and reduce it to the current problem
   (not the other way!)

Question 20

[3SAT Definition]
What is the 3SAT problem?
Input & Output

Answer 20

Boolean satisfiability problem

Input: Conjunctive Normal Form (CNF) with the constraint that each clause has at most 3 literals.

Output: Satisfying assignment if one exists, or “NO” if none exists.

Question 21

[3SAT in NP]

How do we prove that 3SAT is in the class NP?

Answer 21

Show we can verify a proposed solution in polynomial time.

For 3SAT, given a solution S with truth assignments:
1. Check that at least one literal in each clause is satisfied for all clauses.
2. Runtime: Since each clause has at most 3 literals, this takes O(1) time per clause. With m clauses, verification takes O(m) total time, which is polynomial

Question 22

[Reduction]

In the reduction from SAT to 3SAT, what is the direction of the reduction and why?

Answer 22

Reduce SAT to 3SAT (SAT → 3SAT), not the other way around.

The direction is important because we need to show that “if SAT is hard, then 3SAT is hard.” By reducing from SAT (known to be NP-complete) to 3SAT, we show that 3SAT is at least as hard as SAT. This establishes that 3SAT is NP-hard, and combined with showing 3SAT is in NP, proves it is NP-complete.

Question 23

[Reduction]

How to reduce SAT to 3SAT (high level)

Answer 23

Transform clauses with more than 3 literals into clauses with at most 3 literals.

Introduce new variables and creating a sequence of smaller clauses that maintain the logical equivalence.

Question 24

[SAT to 3SAT]

For a clause with 4 literals (a, b, c, d), how would you transform it into clauses with at most 3 literals?

Answer 24

(a ∨ b ∨ y) ∧ (¬y ∨ c ∨ d)

Question 25

[Auxiliary Variables] NEEDS BETTER ANSWER What role do auxiliary variables play in the SAT to 3SAT reduction?

Answer 25

Auxiliary variables serve as connectors between smaller clauses when breaking down large clauses.

Question 26

[SAT to 3SAT] T/F: Each auxiliary variable affects multiple clause transformations

Answer 26

False When we transform a clause with more than 3 literals, we introduce new variables that help maintain the logical equivalence between the original clause and the new set of smaller clauses. Each auxiliary variable is unique to its specific clause transformation and doesn't affect other clause transformations. For example, if we have two large clauses in our original formula: C₁ = (x₁ ∨ x₂ ∨ x₃ ∨ x₄) C₂ = (x₅ ∨ x₆ ∨ x₇ ∨ x₈) We would transform them separately: C₁ becomes (x₁ ∨ x₂ ∨ y₁) ∧ (¬y₁ ∨ x₃ ∨ x₄) C₂ becomes (x₅ ∨ x₆ ∨ y₂) ∧ (¬y₂ ∨ x₇ ∨ x₈)

Question 27

[SAT to 3SAT] For a clause with k literals, how many new variables and clauses are needed in the SAT to 3SAT reduction?

Answer 27

k-3 new variables k-2 clauses to replace original SAT For example, a clause with 4 literals needs 1 new variable and becomes 2 clauses. A clause with 5 literals needs 2 new variables and becomes 3 clauses.

Question 28

[General Transformation Rule] How many vars + clauses needed for SAT with 4 literals

Answer 28

1 new variable and 2 clauses (a, b, c, d) (a ∨ b ∨ y) ∧ (¬y ∨ c ∨ d)

Question 29

[General Transformation Rule] How many vars + clauses needed for SAT with 5 literals

Answer 29

2 new variables and 3 clauses (a, b, c, d, e) (a ∨ b ∨ y) ∧ (¬y ∨ c ∨ z) ∧ (¬z ∨ d ∨ e)

Question 30

[Proof Structure] Why do we need bidirectional proof?

Answer 30

Establishes an "if and only if" relationship between the satisfiability of the original and transformed formulas.

Question 31

[SAT -> 3SAT] B -> A strategy for proof

Answer 31

Take a satisfying assignment for the original clause C and construct a satisfying assignment for the transformed clause(s) C'. The strategy involves identifying which literal in C is satisfied, and then setting the auxiliary variables appropriately to ensure all clauses in C' are satisfied. We set auxiliary variables before the satisfied literal to true and those after to false.

Question 32

[SAT -> 3SAT] What is the strategy for proving the reverse direction in the correctness proof (if C' is satisfiable, then C is satisfiable)?

Answer 32

Proof by contradiction: Assume all literals in the original clause C are false and show this leads to a contradiction in satisfying C'.

Question 33

[SAT Reverse Proof Strategy] PbC: "Assume all literals in the original clause C are false and show this leads to a contradiction in satisfying C'." Explain how proof by contradiction proves reverse satisfiability

Answer 33

If all literals in C are false, then we show that the auxiliary variables must be set in a way that makes it impossible to satisfy all clauses in C', contradicting our assumption. This proves that at least one literal in C must be true, making C satisfiable.

Question 34

[Reduction] T/F: In the SAT to 3SAT reduction, every clause in the original formula must be transformed, even if it already has 3 or fewer literals.

Answer 34

False Clauses that already have 3 or fewer literals can be kept as is in the transformed formula. Only clauses with more than 3 literals need to be transformed.

Question 35

[Verifying Runtime] What is the time complexity of verifying a proposed solution to a 3SAT problem with m clauses? a) O(1) b) O(m) c) O(n), where n is the number of variables d) O(mn)

Answer 35

b) O(m) Verification requires checking each clause to ensure at least one literal is satisfied. Since each clause has at most 3 literals, checking a single clause takes constant time O(1). With m clauses, the total verification time is O(m).

Question 36

[Reduction] In the transformation of a clause with 5 literals, how many auxiliary variables and clauses are needed? a) 2 variables, 2 clauses b) 2 variables, 3 clauses c) 3 variables, 2 clauses d) 3 variables, 3 clauses

Answer 36

b) 2 variables, 3 clauses k-3 vars, k-2 clauses

Question 37

[SAT to 3SAT] Given sat with vars a_1 ... a_k, For a transformed clause with k literals, what is the pattern for the first and last clauses in the resulting sequence?

Answer 37

First clause: (a₁ ∨ a₂ ∨ y₁) Last clause: (¬y_{k-3} ∨ a_{k-1} ∨ a_k) The first clause combines the first two literals with the first auxiliary variable. The last clause combines the negation of the last auxiliary variable with the last two literals from the original clause.

Question 38

[SAT to 3SAT] For a transformed clause with k literals, what is the pattern for the intermediate clauses?

Answer 38

(¬y_i ∨ a_i+2 ∨ ¬y_i+1) "not y i, a i plus 2, not y i plus 1" Each intermediate clause contains the negation of the previous auxiliary variable, the next literal from the original clause, and the next auxiliary variable. This creates a chain of clauses connected by the auxiliary variables.

Question 39

[SAT to 3SAT] Runtime of input transformation

Answer 39

O(nm) In the worst case, each of the m clauses might have n literals, requiring O(n) new variables per clause for a total of O(nm) variables.

Question 40

[NP] T/F: If we can solve the 3SAT problem in polynomial time, then we can solve every problem in NP in polynomial time.

Answer 40

True Since 3SAT is NP-complete, every problem in NP can be reduced to 3SAT. If we had a polynomial-time algorithm for 3SAT, we could use these reductions to solve any problem in NP in polynomial time, which would prove P=NP.

Question 41

[NP] 3SAT is known to be solvable in poly-time

Answer 41

False 3SAT is NP-complete, which means: It belongs to the class NP (solutions can be verified in polynomial time) Every problem in NP can be reduced to 3SAT in polynomial time

Question 42

[NP] Differences between P, NP, NP-Complete and NP-Hard

Answer 42

P = solvable in polytime NP= verifiable in polytime NP-Complete = in NP & any NP problem can be reduced to it in polytime NP-Hard = 1. May or may not be in NP 2. May or may not be verifiable in polytime

Question 43

[NP] Why is Knapsack not in NP

Answer 43

It takes pseudo polynomial time to verify the answer O(nB).

Question 44

Proof of Correctness pairs

Answer 44

B -> A & A -> B B -> A & !B -> !A !A -> !B & A -> B !A -> !B & !B -> !A

Question 45

Independent Set Input & Output

Answer 45

Input: G=(V,E) + goal g Output: IS of size at least g

Question 46

Independent Set NP proof

Answer 46

Given input G, g & solution S: 1. For all pairs (x,y) in S, check that (x,y) not in E. Takes O(n^2). 2. Check size of S is at least g. Takes O(n)

Question 47

Independent Set 3SAT -> IS Input Transform + Runtime

Answer 47

* Consider 3SAT input f with variables x1 ... xn and clauses c1 ... cn. Each clause has size at most 3. For each c in C, create a subgraph where each literal become vertices and all vertices within the clause are connected. For each literal in c, add an edge from it to any other literals across all clauses that share the same variable. Set IS goal g equal to the number of clauses in 3SAT input. Pass the new graph and g to IS. * Let n be the numer of literals in 3SAT, then creating vertices for all literals take O(n). Adding an edge within each subgraph takes O(m) since there is at most 3 literals in each clause. Adding variable edges take O(m^2) edges since worst case all variables appear in every clause.

Question 48

Independent Set 3SAT -> IS Output Transform + Runtime

Answer 48

If IS returns NO, return NO for 3SAT. If IS returns solution vertex set S, choose 1 vertex in each clause that is in S and set satisfying assignment. This takes O(m) time.

Question 49

3SAT -> Independent Set Proof A -> B

Answer 49

If 3SAT has a solution, IS has a solution. * If 3SAT has a solution, at least one satisfied literal in each clause is mapped to a vertex in IS. * Size S is m (# clauses), we take exactly one from each clause, so required size is met * Assignment’s truth values are for a variable (not literal) so we wouldn’t add both x_i and !x_i simultaneously, ensuring no contradictions. * No clause / variables edges are valid candidates for S, which ensures no edges between vertices in S

Question 50

Independent Set Proof B -> A

Answer 50

* If IS has a solution, 3SAT has a solution. IS selects exactly one vertex in each subgraph which maps to clauses in 3SAT. Since there is 1 satisfying assignment for each clause, all clauses are satisfied in 3SAT. * IS will not choose assignments that would cause a contradiction because the input transformation adds an edge between all shared variables, thus IS will not select both a literal and its negation as part of its solution.

Question 51

AtMost-3SAT Input & Output

Answer 51

Input: CNF such that each clause has at most three literals, and each variable appears at most three times. Output: Satisfying assignments or NO.

Question 52

AtMost-3SAT NP Proof

Answer 52

First we show that AtMost-3SAT is in class NP. Given solution S with satisfying assignments, for each clause c∈C check that at least 1 literal is satisfied. Let m be the number of clauses in C. Checking all clauses takes O(m) since each clause has at most 3 literals.

Question 53

AtMost-3SAT 3SAT -> AtMost-3SAT Input Transformation

Answer 53

1. For each variable x_i in 3SAT input, replace each literal x_i and !x_i with new variables y_i1, y_i2 ... y_ik. 2. Create new set of clauses (y_i1 ^ !y_i2) v (y_i2 ^ !y_i3) ... (y_ik ^ y_i1). Join the modified 3SAT input CNF with the new clauses and pass to AtMost3SAT. 3. This procedure creates at most O(nm) new variables and O(nm) new clauses. O(nm) + O(nm) = O(nm) which is polynomial.

Question 54

AtMost-3SAT 3SAT -> AtMost-3SAT Output Transformation

Answer 54

If AtMost3SAT returns NO, return NO for 3SAT. If AtMost3SAT returns a solution, assignments for all new variables added for an original variable is expected to be the same. Thus, map back assignments for y_i1 ... y_ik back to original variable x. We perform this operation for each variable, thus takes O(n) time.

Question 55

AtMost-3SAT 3SAT -> AtMost-3SAT Proof of Correctness A -> B

Answer 55

* If 3SAT has a satisfying assignment then AtMost3SAT is satisfied. By replacing literals with new variables y_i1 ... y_ik and adding a set of clauses for y_i, we ensure that the assignment of all replacement variables is the same. * Consider (y_i1 v !y_i2), if y_i1 is False, then y_i2 must be False satisfy the clause. Then (y_i2 v !y_i3) since y_i2 is False y_i3 must be False to satisfy the clause, we continue this up to (y_ik v !y_i1). Since y_i1 was set set to False its negation is True and thus it is satisfied. The same logic applies when y_i1 ... y_ik is set to True, all variables must be True. * Thus, since we force all new variables for an original variable to have the same assignment, we maintain logical equivalence between 3SAT and AtMost3SAT. Thus if 3SAT is satisfied AtMost3SAT is satisfied.

Question 56

AtMost-3SAT 3SAT -> AtMost-3SAT Proof of Correctness !A -> !B

Answer 56

If 3SAT has no solution then AtMost3SAT has no solution. As shown before, the mapping of variables maintains logical equivalence, thus if there is no satisfying assignment for 3SAT then there is no satisfying assignment for AtMost3SAT.

Question 57

What is the relationship between Vertex Cover and Independent Set?

Answer 57

The complement to VC is the Independent Set If S is a vertex cover of graph G, then V-S (the vertices not in S) must form an independent set.

Question 58

What is the relationship between Clique and Independent Set?

Answer 58

An IS in graph G is equal to a clique in reverse graph G-bar

Question 59

T/F 3SAT can be solved in polynomial time

Answer 59

True, if all variables appear at most once DPV 8.6, solved by max-flow where variables on one side, clauses on other side (solving this won't be on exam)

Question 60

Why does a Clique of size k have exactly k(k-1)/2 edges

Answer 60

In a k-vertex clique: 1. Each vertex must connect to all other k-1 vertices 2. This creates k(k-1) connections when counting from all vertices 3. Since each edge is counted twice (once from each endpoint), the actual edge count is k(k-1)/2

Question 61

Difference between a subgraph and induced subgraph with respect to a NP solution?

Answer 61

Subgraph = An actual graph, G=(V,E), can leave out edges Induced Subgraph = set of vertices which we induce a subgraph. All connecting edges between vertices will be added.

Question 62

Define search problem

Answer 62

Problem where we can efficiently verify solutions

Question 63

Diff between search & decision problem

Answer 63

Decision: Yes / no feasible

Question 64

(True/False) True or False: The contrapositive of "if P, then Q" is "if not P, then not Q".

Answer 64

False. The contrapositive of "if P, then Q" is "if not Q, then not P". The statement "if not P, then not Q" is the inverse of the original statement.

Question 65

[Vertex Cover] IFF relationship btw VC and IS

Answer 65

For all (x,y) in E, AT LEAST one endpoint is in VC set S. Therefore AT MOST one of x,y is in its complement S-bar. This means that no edge of the graph is contained in S-bar, thus S-bar is an IS.

Question 66

[NP Classes] Valid reduction patterns

Answer 66

1. NP-Complete → NP-Complete: Always possible 2. P → NP-Complete: Possible but not useful for proofs 3. P → P: Always possible

Question 67

Invalid reduction patterns

Answer 67

NP-Complete → P: Not possible (if P != NP) NP-Hard → P: Not possible

Question 68

How to make k-SPANNING TREE problem solvable in poly-time

Answer 68

problem is solvable in polynomial time for larger fixed values of k.

Question 69

How to make SAT problems solvable in poly-time

Answer 69

Make each literal appear at most once

Question 70

Why can the Vertex Cover problem be NP-complete, yet finding a vertex cover of size at most 20 can be done in polynomial time?

Answer 70

These refer to different problems: 1. General Vertex Cover (NP-complete): The budget b is part of the input that can be any value. 2. Fixed-parameter Vertex Cover (in P): When b=20 is fixed and not part of the input, we can solve it in polynomial time.

Question 71

An NP-Complete problem can become P by setting what was a parameter with respect to the input to a fixed constant

Answer 71

True The general problem with variable parameter b is in complexity class NP-Complete The restricted problem with fixed constant parameter (e.g., b=20) is in complexity class P

Question 72

If problem A reduces to problem B in polynomial time, what can we conclude about their relative difficulty?

Answer 72

* B is at least as hard as A * Any efficient algorithm for B would yield an efficient algorithm for A

Question 73

Significance of converting NP-Hard problem to NP-Complete (TSP to TSP-search)?

Answer 73

By reducing a NP-hard problem into a NP-Complete, if we can ever find an algo that runs in polynomial time to solve NP-Complete version then we can solve NP-Hard problem in poly-time too.

Question 74

[Clique] Runtime of verification

Answer 74

O(n^2) For all pairs in S, check (x,y) in E

Question 75

Rudrata Path -> Longest Path idea I/O

Answer 75

I: Pass G and g=n-1 to Longest Path O: Return solution as-is

Question 76

Rudrata Path -> Longest Path idea Correctness

Answer 76

Rudrata path covers all v in V, so its path is n-1. Finding longest path of n-1 will always return Rudrata Path if it exists

Question 77

Rudrata Path -> Rudrata Cycle I/O

Answer 77

I: Add new edge x and edges (x, s) and (x, t) O: Remove x, (x,s) and (x,t) to break cycle, and return path