NP (AI generated from transcript) Flashcards
What does NP stand for in complexity theory?
Nondeterministic Polynomial time
True or False: NP means ‘Not Polynomial’ time.
False
Which complexity class is a subset of the other? A) P is a subset of NP B) NP is a subset of P
A) P is a subset of NP
If P = NP, which of the following is true? A) All NP-Complete problems can be solved in polynomial time B) No NP-Complete problems can be solved in polynomial time
A) All NP-Complete problems can be solved in polynomial time
To prove a problem is in NP, what must be demonstrated?
That a proposed solution can be verified in polynomial time
For a problem to be NP-Complete, which conditions must be satisfied? A) It is in NP B) All problems in NP reduce to it C) Both A and B D) Either A or B
C) Both A and B
If problem A reduces to problem B, and B is in P, what can we conclude about A?
A is in P
In a reduction from problem A to problem B, the reduction arrow points: A) From A to B B) From B to A
A) From A to B
To verify a clique of size k in a graph with n vertices, the time complexity is:
O(n²)
In a reduction, which transformations must run in polynomial time?
Both input and output transformations
True or False: When showing an ‘if and only if’ relationship in a reduction proof, proving ‘if A has a solution then B has a solution’ and ‘if B has no solution then A has no solution’ is sufficient.
False
The statement mixes one direction (A → B) with the contrapositive of the other direction (¬B → ¬A).
Would be valid if “A -> B” and “B -> A”, or “A -> B” and “!A -> !B”
Which of the following problems is in P?
1. MST
2. Knapsack-search
3. k-Coloring
4. SAT
Minimum Spanning Tree
When proving a graph problem is NP-Complete, which problems are typically best to reduce from?
Independent Set, Clique, or Vertex Cover
The time complexity to verify a solution to the Subset Sum problem is:
O(n log W) where W is the sum of the integers
True or False: In a reduction, we transform the input of the problem we’re proving is NP-Complete to the input of the known NP-Complete problem.
False
When reducing SAT to 3SAT, what is the main transformation technique?
Splitting clauses with more than three literals by introducing new variables
The contrapositive of ‘If P then Q’ is:
If not Q then not P
Which statement about NP-Hard problems is correct?
1. All NP Hard problems are NP-Complete
2. All NP-Hard problems are in NP
3. NP Hard can be verified in polynomial time
4. Not all NP-Hard problems are in NP
Not all NP-Hard problems are in NP
In the reduction from 3SAT to Independent Set, the goal value g is set to:
The number of clauses in the 3SAT formula
In the reduction from Independent Set to Vertex Cover, how is the budget b determined?
b = n - g (where n is the number of vertices)
True or False: In the reduction from Independent Set to Clique, we use the complement of the original graph.
True
Complement Graph:
The complement of a graph is a graph with the same vertices, but where an edge exists between two vertices if and only if it did not exist in the original graph
In the reduction from 3SAT to Subset Sum, what number base is used to avoid carries between digits?
Base 10
Which of the following is NOT in NP?
Maximum Independent Set (optimization version)
The time complexity to verify a Vertex Cover solution is:
(Given a candidate solution for VC of vertex set S and input graph G=(V,E), check that for all edges (x,y) in E, at least x or y is in vertex set S.)
O(n + m) where n is vertices and m is edges
Given n vertices in V and m edges in E, this check takes O(n+m). We then check that size of S is at most budget b by counting the number of vertices in S. Counting all vertices takes O(n) time. O(n+m) dominates and is polynomial.
True or False: If problem A reduces to problem B, then A is computationally at least as hard as B.
False (B is at least as hard as A)
When reducing from SAT, which variant is typically more convenient to use?
3SAT
In a reduction from problem A to problem B, if B has a solution, what can we conclude about A?
A has a solution
Most egregious error in NP-Completeness proofs
Reducing from the unknown problem to a known NP-Complete problem
True or False: When verifying a solution for a problem is in NP, the verification runtime can depend on the goal/budget parameter.
False
Which pair of statements proves the ‘if and only if’ relationship in a correctness proof?
‘If A has a solution, then B has a solution’ AND ‘If B has a solution, then A has a solution’
The runtime of a verification algorithm for an NP problem must be:
Polynomial in the input size
True or False: In a reduction, the input transformation must maintain the same problem size.
False
In the reduction from 3SAT to Independent Set, what edges are added between literals of different clauses of same variables?
Edges between a literal and its negation
True or False: A problem can be NP-Hard without being in NP.
True
The runtime of verifying a solution to 3SAT with n variables and m clauses is:
O(m)
Given assignments S, check that each clause in C has at least 1 satisfied literal. Since each clause has at most 3 literals, it takes O(1) to check each clause, and there are m clauses so it’d take O(m) time which is polynomial.
True or False: The Knapsack search problem is NP-Complete.
True
Which is the correct relationship? A) P ⊆ NP B) NP ⊆ P
A) P ⊆ NP
For the Subset Sum problem with n integers and target sum t, the dynamic programming algorithm runtime is:
O(nt)
True or False: The decision version of optimization problems is typically used in NP-Completeness proofs.
True
In the reduction from 3SAT to Subset Sum, what are ‘buffer numbers’ used for?
To adjust the sum to the target when not all literals in a clause are satisfied
True or False: Max Independent Set is NP-Complete.
False (it’s NP-Hard but not in NP)
In the reduction from Independent Set to Vertex Cover, if S is a vertex cover, what is its relationship to the independent set?
The complement of S is an independent set
Which problem is typically used to prove Knapsack is NP-Complete?
Subset Sum
True or False: The SAT problem remains NP-Complete when restricted to formulas where each literal appears at most twice.
True
What property must a reduction from problem A to problem B maintain for correctness?
If and only if A has a solution, B has a solution
In CNF formulas, clauses are connected by which operator?
AND (∧)
In the Kite problem, what defines a kite in a graph with 2n vertices?
n vertices form a clique and n vertices form a path connected to the clique
True or False: In the reduction from 3SAT to Independent Set, each clause is represented as a complete subgraph.
True
Which of the following correctly describes the relationship between P, NP, and NP-Complete?
NP-Complete = NP ∩ NP-Hard
The time complexity for verifying a solution to the Subgraph Isomorphism problem is:
For a pair of graph G=(V,E) and H=(V’,E’) Let π be the mapping from V to V’. First, traverse graph G. For each vertex v ∈ V, check if π(v)=v’ exists in H. For each edge (v, u) adjacent to v, check all edges adjacent to v’ to find (v’, u’).
O((n+m)m’)
Traversing G takes O(n+m). For each edge we have m’ edges (of size E’) to check. This results in O(n+m * m’) which is polynomial.
In a reduction from Independent Set to Clique+IS, why is the goal set to k+1 instead of k?
By adding a new vertex and connecting it to the clique, we ensure that the transformed graph G’ has a clique of size k+1, and the original independent set (if it exists) remains an independent set of size k, thus satisfying the conditions of the Clique+IS problem
True or False: An algorithm with runtime O(nW), where W is an input parameter, is a polynomial time algorithm.
False (it’s pseudo-polynomial)
Which of the following is NOT a constraint in AtMost-3SAT?
Each variable must appear at least once
In reduction by generalization, what is the approach?
Showing that the new problem is a more general case of a known NP-Complete problem
True or False: Every NP-Complete problem reduces to every other NP-Complete problem.
True
The input size for Subset Sum problem with n integers up to value t is:
O(n log t)
In the reduction from SAT to 3SAT, how many new variables are needed for a clause with k literals?
k-3
True or False: In the reduction from Vertex Cover to Hitting Set, each edge becomes a set in the Hitting Set instance.
True
Which of the following is NOT a valid way to prove the ‘if and only if’ correctness?
If A has a solution then B has a solution, and if A has a solution then B has no solution
In the reduction from 3SAT to Independent Set, the number of vertices in the resulting graph is:
At most 3m (where m is the number of clauses)
True or False: When reducing from 3SAT to Subset Sum, the target sum has a digit pattern that corresponds to variables and clauses.
True
The relationship between CLIQUE and INDEPENDENT SET is:
A set S is a clique in G if and only if S is an independent set in the complement of G (G-bar)
In the EXACT 4SAT problem, what is the constraint on clauses?
Each clause has exactly 4 literals
True or False: A solution to the Subset Sum problem can be verified in O(n log t) time.
True
In the reduction from Subset Sum to Knapsack, how are the weights and values related?
Weights and values are equal to the integers in the Subset Sum instance
Which of the following is NOT a verification step for the Kite problem?
Checking if the graph has a Hamiltonian cycle
True or False: The reduction from SAT to 3SAT creates at most O(nm) new clauses.
True
Let C=a1…an be input to I to SAT, and c′∈C′ be clauses in our input to 3SAT. For each c′∈C′, if c’ has at most 3 literals, add c as clause c’ to C’. If c has greater than 3 literals, create c’ as follows: create k-3 new variables as y1,y2…yk−3. Using these variables create C′=(a1,a2,y1)∧(yˉ1,a3,y2)…(yˉk−4,ak−2,yk−3)∧(yk−3,ak−1,ak). There are m clauses with at most n literals so takes O(nm) which is polynomial.
Which statement about the converse of ‘If P then Q’ is correct?
The converse ‘If Q then P’ is not logically equivalent to the original statement
In gadget construction for reductions, what is the purpose of a gadget?
To transform one problem instance into another while preserving solution properties
True or False: The runtime of a verification algorithm can depend on the magnitude of input values.
True
In the reduction from 3SAT to Independent Set, what ensures that no contradictory variable assignments are made?
Adding edges between vertices representing a variable and its negation
The number of different ways to prove an ‘if and only if’ relationship is:
4
True or False: In the reduction from 3SAT to Subset Sum, the transformation creates O(nm) numbers.
True
Which of the following problems would be best to reduce from when proving Vertex Cover is NP-Complete?
Independent Set
In the context of NP-Completeness, what does a subgraph need to satisfy compared to an induced subgraph?
A subgraph can omit edges between its vertices that exist in the original graph
True or False: In the reduction from Independent Set to Clique, isolated vertices become connected to all other vertices in the complement graph.
True
Given input G=(V,E) and goal g as input to IS, modify it to create a complementary graph (G’). Given G, we invert it by checking for all pairs x,y in V whether (x,y) is in E. If (x,y) is in E, remove this edge and if (x,y) is not in E, we add a new edge.
Given n vertices, this operation takes O(n^2). Set goal g for Clique equal to IS goal g. This takes O(1) time. Pass the G’ and goal g to Clique. Runtime is dominated by O(n^2) and polynomial in time.
Which is NOT a valid statement about NP-Completeness?
If a problem is NP-Complete, there must be no polynomial time algorithm for it
In SAT, literals within a clause are connected by which operator?
OR (∨)
True or False: The Clique problem restricted to graphs where every vertex has degree at most 3 is in P.
True
DPV shows it can be solved checking all combinations of 3 vertices
When reducing from a known NP-Complete problem A to an unknown problem B, what is the correct statement about their relative hardness?
B is at least as hard as A
In the reduction from 3SAT to Subset Sum, what happens if a clause has no satisfied literals?
The corresponding digit cannot sum to the target value
For the Vertex Cover problem, what is search component
Finding a vertex cover at most budget b
In the reduction from Clique to Kite, what structure is added to the original graph?
A path connected to each vertex
True or False: Cook-Levin theorem established that SAT is NP-Complete.
True
The NotAllEqual-3SAT problem differs from 3SAT by requiring:
Each clause must have at least one true literal and at least one false literal
Which reduction technique is used when transforming an optimization problem to a decision problem?
Adding a budget/goal parameter
True or False: In proving a problem is NP-Complete, it’s sufficient to show that the known NP-Complete problem reduces to it.
False
When a problem has a dynamic programming solution with runtime O(nW), it is:
Pseudo-polynomial, not necessarily polynomial
In the context of NP-Completeness, what does ‘polynomial’ refer to?
Runtime that is polynomial in the input size
True or False: Exact-4SAT is NP-Complete.
True
If we have a polynomial time algorithm for an NP-Complete problem, what can we conclude?
P = NP
In the reduction from Independent Set to Vertex Cover, the runtime of the input transformation is:
O(1)
set b = n - g
True or False: Knapsack with inputs given in unary is in P.
True
The purpose of ‘variable edges’ in the 3SAT to Independent Set reduction is:
To prevent selecting both a variable and its negation
NP-Hard key fact
NP-Hard problems are at least as hard as any problem in NP
True or False: If a problem is in P, it must also be in NP.
True
In the reduction from SAT to 3SAT, how many new clauses replace a clause with k literals?
k-2
What does the ‘completeness’ in NP-Complete signify?
The problem is both in NP and NP-Hard
True or False: STINGY SAT (finding a satisfying assignment with at most k true variables) is NP-Complete.
True
If problem A reduces to problem B and problem B reduces to problem C, what can we conclude?
Problem A reduces to problem C
