NP Flashcards
How to show a problem is in NP
Algorithm must be provided that can verify proposed solution (S) given an instance (I) efficiently in polynomial time relative to the size of I.
[SAT]
Input
Boolean formula in CNF with n variables and m clause
[SAT]
Output
Satisfying assignment or NO
[SAT]
NP Proof - Show that SAT is in NP
Given f & assignment x1 … xn:
O(n) time to check that a clause is satisfied for m clauses.
O(nm) total time to verify.
[3SAT]
NP Proof - Show that 3SAT is in NP
Given f & assignment x1 … xn:
Check a clause is satisfied O(1) (bc size of clauses is bounded by a constant)
m clauses, so O(m) and polynomial
[Colorings]
Show that k-colorings is in NP
Given a k-coloring, check each edge to ensure endpoints have different colors, O(n+m)
[MST]
Proof that MST is in NP
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)
[MST]
How to prove MST is in P
Prove can solve in poly-time by running Kruskals
[Knapsack, original]
How to verify solution S
sum of weight <= B & sum of value is maximum
[Knapsack]
Why is knapsack not known to be in NP?
No poly-time method exists to verify value sum is maximal.
DP approach takes O(nB) time which is exponential relative to input size.
[Knapsack search]
Difference from original knapsack
Instead of max value sum, verify that subset S exists with at least goal value g and at most weight W
[Knapsack search vs optimization]
How to prove goal value
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)
T/F
If the knapsack search version is solvable in polynomial time, so is the original optimization problem.
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
[NP]
Significance of P != NP
There are problems that exist outside the class P (solvable in polynomial time), which are termed intractable or NP-complete
[NP]
Contrapositive of “If P != NP, then all NP-complete problems are not in P”
“If a NP-complete problem can be solved in poly-time, then all problems in NP can be solved in poly-time”
T/F
SAT is not in P
True. Considered most difficult problem in NP.
[Reduction]
A -> B in words
If A has a solution then B has a solution
[Reduction]
Key components for a reduction
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.
[Reduction]
How to prove NP-Completeness
- Verify in poly-time
- Use an existing NP-Complete problem and reduce it to the current problem
(not the other way!)
[3SAT Definition]
What is the 3SAT problem?
Input & Output
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.
[3SAT in NP]
How do we prove that 3SAT is in the class NP?
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
[Reduction]
In the reduction from SAT to 3SAT, what is the direction of the reduction and why?
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.
[Reduction]
How to reduce SAT to 3SAT (high level)
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.
[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?
(a ∨ b ∨ y) ∧ (¬y ∨ c ∨ d)
[Auxiliary Variables]
NEEDS BETTER ANSWER
What role do auxiliary variables play in the SAT to 3SAT reduction?
Auxiliary variables serve as connectors between smaller clauses when breaking down large clauses.
[SAT to 3SAT]
T/F: Each auxiliary variable affects multiple clause transformations
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₈)
[SAT to 3SAT]
For a clause with k literals, how many new variables and clauses are needed in the SAT to 3SAT reduction?
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.
[General Transformation Rule]
How many vars + clauses needed for SAT with 4 literals
1 new variable and 2 clauses
(a, b, c, d)
(a ∨ b ∨ y) ∧ (¬y ∨ c ∨ d)
[General Transformation Rule]
How many vars + clauses needed for SAT with 5 literals
2 new variables and 3 clauses
(a, b, c, d, e)
(a ∨ b ∨ y) ∧ (¬y ∨ c ∨ z) ∧ (¬z ∨ d ∨ e)
[Proof Structure]
Why do we need bidirectional proof?
Establishes an “if and only if” relationship between the satisfiability of the original and transformed formulas.
[SAT -> 3SAT]
B -> A strategy for proof
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.
[SAT -> 3SAT]
What is the strategy for proving the reverse direction in the correctness proof (if C’ is satisfiable, then C is satisfiable)?
Proof by contradiction: Assume all literals in the original clause C are false and show this leads to a contradiction in satisfying C’.
[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
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.
[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.
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.
[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)
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).
[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
b) 2 variables, 3 clauses
k-3 vars, k-2 clauses
[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?
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.
[SAT to 3SAT]
For a transformed clause with k literals, what is the pattern for the intermediate clauses?
(¬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.
[SAT to 3SAT]
Runtime of input transformation
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.
[NP]
T/F: If we can solve the 3SAT problem in polynomial time, then we can solve every problem in NP in polynomial time.
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.
[NP]
3SAT is known to be solvable in poly-time
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
[NP]
Differences between P, NP, NP-Complete and NP-Hard
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
[NP]
Why is Knapsack not in NP
It takes pseudo polynomial time to verify the answer O(nB).
Proof of Correctness pairs
B -> A & A -> B
B -> A & !B -> !A
!A -> !B & A -> B
!A -> !B & !B -> !A
Independent Set
Input & Output
Input: G=(V,E) + goal g
Output: IS of size at least g
Independent Set
NP proof
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)
Independent Set
3SAT -> IS
Input Transform + Runtime
- 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.
Independent Set
3SAT -> IS
Output Transform + Runtime
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.
3SAT -> Independent Set Proof
A -> B
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
Independent Set Proof
B -> A
- 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.
AtMost-3SAT
Input & Output
Input: CNF such that each clause has at most three literals, and each variable appears at most three times.
Output: Satisfying assignments or NO.
AtMost-3SAT
NP Proof
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.
AtMost-3SAT
3SAT -> AtMost-3SAT
Input Transformation
- 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.
- 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.
- This procedure creates at most O(nm) new variables and O(nm) new clauses. O(nm) + O(nm) = O(nm) which is polynomial.
AtMost-3SAT
3SAT -> AtMost-3SAT
Output Transformation
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.
AtMost-3SAT
3SAT -> AtMost-3SAT
Proof of Correctness
A -> B
- 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.
AtMost-3SAT
3SAT -> AtMost-3SAT
Proof of Correctness
!A -> !B
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.
What is the relationship between Vertex Cover and Independent Set?
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.
What is the relationship between Clique and Independent Set?
An IS in graph G is equal to a clique in reverse graph G-bar
T/F
3SAT can be solved in polynomial time
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)
Why does a Clique of size k have exactly k(k-1)/2 edges
In a k-vertex clique:
- Each vertex must connect to all other k-1 vertices
- This creates k(k-1) connections when counting from all vertices
- Since each edge is counted twice (once from each endpoint), the actual edge count is k(k-1)/2
Difference between a subgraph and induced subgraph with respect to a NP solution?
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.
Define search problem
Problem where we can efficiently verify solutions
Diff between search & decision problem
Decision: Yes / no feasible
(True/False)
True or False: The contrapositive of “if P, then Q” is “if not P, then not Q”.
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.
[Vertex Cover]
IFF relationship btw VC and IS
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.
[NP Classes]
Valid reduction patterns
- NP-Complete → NP-Complete: Always possible
- P → NP-Complete: Possible but not useful for proofs
- P → P: Always possible
Invalid reduction patterns
NP-Complete → P: Not possible (if P != NP)
NP-Hard → P: Not possible
How to make k-SPANNING TREE problem solvable in poly-time
problem is solvable in polynomial time for larger fixed values of k.
How to make SAT problems solvable in poly-time
Make each literal appear at most once
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?
These refer to different problems:
- General Vertex Cover (NP-complete): The budget b is part of the input that can be any value.
- Fixed-parameter Vertex Cover (in P): When b=20 is fixed and not part of the input, we can solve it in polynomial time.
An NP-Complete problem can become P by setting what was a parameter with respect to the input to a fixed constant
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
If problem A reduces to problem B in polynomial time, what can we conclude about their relative difficulty?
- B is at least as hard as A
- Any efficient algorithm for B would yield an efficient algorithm for A
Significance of converting NP-Hard problem to NP-Complete (TSP to TSP-search)?
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.
[Clique]
Runtime of verification
O(n^2)
For all pairs in S, check (x,y) in E
Rudrata Path -> Longest Path idea I/O
I: Pass G and g=n-1 to Longest Path
O: Return solution as-is
Rudrata Path -> Longest Path idea Correctness
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
Rudrata Path -> Rudrata Cycle I/O
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
