NP (AI generated from transcript)

Question 1

What does NP stand for in complexity theory?

Answer 1

Nondeterministic Polynomial time

Question 2

True or False: NP means ‘Not Polynomial’ time.

Answer 2

False

Question 3

Which complexity class is a subset of the other? A) P is a subset of NP B) NP is a subset of P

Answer 3

A) P is a subset of NP

Question 4

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

Answer 4

A) All NP-Complete problems can be solved in polynomial time

Question 5

To prove a problem is in NP, what must be demonstrated?

Answer 5

That a proposed solution can be verified in polynomial time

Question 6

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

Answer 6

C) Both A and B

Question 7

If problem A reduces to problem B, and B is in P, what can we conclude about A?

Answer 7

A is in P

Question 8

In a reduction from problem A to problem B, the reduction arrow points: A) From A to B B) From B to A

Answer 8

A) From A to B

Question 9

To verify a clique of size k in a graph with n vertices, the time complexity is:

Answer 9

O(n²)

Question 10

In a reduction, which transformations must run in polynomial time?

Answer 10

Both input and output transformations

Question 11

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.

Answer 11

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”

Question 12

Which of the following problems is in P?
1. MST
2. Knapsack-search
3. k-Coloring
4. SAT

Answer 12

Minimum Spanning Tree

Question 13

When proving a graph problem is NP-Complete, which problems are typically best to reduce from?

Answer 13

Independent Set, Clique, or Vertex Cover

Question 14

The time complexity to verify a solution to the Subset Sum problem is:

Answer 14

O(n log W) where W is the sum of the integers

Question 15

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.

Answer 15

False

Question 16

When reducing SAT to 3SAT, what is the main transformation technique?

Answer 16

Splitting clauses with more than three literals by introducing new variables

Question 17

The contrapositive of ‘If P then Q’ is:

Answer 17

If not Q then not P

Question 18

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

Answer 18

Not all NP-Hard problems are in NP

Question 19

In the reduction from 3SAT to Independent Set, the goal value g is set to:

Answer 19

The number of clauses in the 3SAT formula

Question 20

In the reduction from Independent Set to Vertex Cover, how is the budget b determined?

Answer 20

b = n - g (where n is the number of vertices)

Question 21

True or False: In the reduction from Independent Set to Clique, we use the complement of the original graph.

Answer 21

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

Question 22

In the reduction from 3SAT to Subset Sum, what number base is used to avoid carries between digits?

Answer 22

Base 10

Question 23

Which of the following is NOT in NP?

Answer 23

Maximum Independent Set (optimization version)

Question 24

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.)

Answer 24

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.

Question 25

True or False: If problem A reduces to problem B, then A is computationally at least as hard as B.

Answer 25

False (B is at least as hard as A)

Question 26

When reducing from SAT, which variant is typically more convenient to use?

Answer 26

3SAT

Question 27

In a reduction from problem A to problem B, if B has a solution, what can we conclude about A?

Answer 27

A has a solution

Question 28

Most egregious error in NP-Completeness proofs

Answer 28

Reducing from the unknown problem to a known NP-Complete problem

Question 29

True or False: When verifying a solution for a problem is in NP, the verification runtime can depend on the goal/budget parameter.

Answer 29

False

Question 30

Which pair of statements proves the 'if and only if' relationship in a correctness proof?

Answer 30

'If A has a solution, then B has a solution' AND 'If B has a solution, then A has a solution'

Question 31

The runtime of a verification algorithm for an NP problem must be:

Answer 31

Polynomial in the input size

Question 32

True or False: In a reduction, the input transformation must maintain the same problem size.

Answer 32

False

Question 33

In the reduction from 3SAT to Independent Set, what edges are added between literals of different clauses of same variables?

Answer 33

Edges between a literal and its negation

Question 34

True or False: A problem can be NP-Hard without being in NP.

Answer 34

True

Question 35

The runtime of verifying a solution to 3SAT with n variables and m clauses is:

Answer 35

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.

Question 36

True or False: The Knapsack search problem is NP-Complete.

Answer 36

True

Question 37

Which is the correct relationship? A) P ⊆ NP B) NP ⊆ P

Answer 37

A) P ⊆ NP

Question 38

For the Subset Sum problem with n integers and target sum t, the dynamic programming algorithm runtime is:

Answer 38

O(nt)

Question 39

True or False: The decision version of optimization problems is typically used in NP-Completeness proofs.

Answer 39

True

Question 40

In the reduction from 3SAT to Subset Sum, what are 'buffer numbers' used for?

Answer 40

To adjust the sum to the target when not all literals in a clause are satisfied

Question 41

True or False: Max Independent Set is NP-Complete.

Answer 41

False (it's NP-Hard but not in NP)

Question 42

In the reduction from Independent Set to Vertex Cover, if S is a vertex cover, what is its relationship to the independent set?

Answer 42

The complement of S is an independent set

Question 43

Which problem is typically used to prove Knapsack is NP-Complete?

Answer 43

Subset Sum

Question 44

True or False: The SAT problem remains NP-Complete when restricted to formulas where each literal appears at most twice.

Answer 44

True

Question 45

What property must a reduction from problem A to problem B maintain for correctness?

Answer 45

If and only if A has a solution, B has a solution

Question 46

In CNF formulas, clauses are connected by which operator?

Answer 46

AND (∧)

Question 47

In the Kite problem, what defines a kite in a graph with 2n vertices?

Answer 47

n vertices form a clique and n vertices form a path connected to the clique

Question 48

True or False: In the reduction from 3SAT to Independent Set, each clause is represented as a complete subgraph.

Answer 48

True

Question 49

Which of the following correctly describes the relationship between P, NP, and NP-Complete?

Answer 49

NP-Complete = NP ∩ NP-Hard

Question 50

The time complexity for verifying a solution to the Subgraph Isomorphism problem is: ## Footnote 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’).

Answer 50

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.

Question 51

In a reduction from Independent Set to Clique+IS, why is the goal set to k+1 instead of k?

Answer 51

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

Question 52

True or False: An algorithm with runtime O(nW), where W is an input parameter, is a polynomial time algorithm.

Answer 52

False (it's pseudo-polynomial)

Question 53

Which of the following is NOT a constraint in AtMost-3SAT?

Answer 53

Each variable must appear at least once

Question 54

In reduction by generalization, what is the approach?

Answer 54

Showing that the new problem is a more general case of a known NP-Complete problem

Question 55

True or False: Every NP-Complete problem reduces to every other NP-Complete problem.

Answer 55

True

Question 56

The input size for Subset Sum problem with n integers up to value t is:

Answer 56

O(n log t)

Question 57

In the reduction from SAT to 3SAT, how many new variables are needed for a clause with k literals?

Answer 57

k-3

Question 58

True or False: In the reduction from Vertex Cover to Hitting Set, each edge becomes a set in the Hitting Set instance.

Answer 58

True

Question 59

Which of the following is NOT a valid way to prove the 'if and only if' correctness?

Answer 59

If A has a solution then B has a solution, and if A has a solution then B has no solution

Question 60

In the reduction from 3SAT to Independent Set, the number of vertices in the resulting graph is:

Answer 60

At most 3m (where m is the number of clauses)

Question 61

True or False: When reducing from 3SAT to Subset Sum, the target sum has a digit pattern that corresponds to variables and clauses.

Answer 61

True

Question 62

The relationship between CLIQUE and INDEPENDENT SET is:

Answer 62

A set S is a clique in G if and only if S is an independent set in the complement of G (G-bar)

Question 63

In the EXACT 4SAT problem, what is the constraint on clauses?

Answer 63

Each clause has exactly 4 literals

Question 64

True or False: A solution to the Subset Sum problem can be verified in O(n log t) time.

Answer 64

True

Question 65

In the reduction from Subset Sum to Knapsack, how are the weights and values related?

Answer 65

Weights and values are equal to the integers in the Subset Sum instance

Question 66

Which of the following is NOT a verification step for the Kite problem?

Answer 66

Checking if the graph has a Hamiltonian cycle

Question 67

True or False: The reduction from SAT to 3SAT creates at most O(nm) new clauses.

Answer 67

True ## Footnote 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.

Question 68

Which statement about the converse of 'If P then Q' is correct?

Answer 68

The converse 'If Q then P' is not logically equivalent to the original statement

Question 69

In gadget construction for reductions, what is the purpose of a gadget?

Answer 69

To transform one problem instance into another while preserving solution properties

Question 70

True or False: The runtime of a verification algorithm can depend on the magnitude of input values.

Answer 70

True

Question 71

In the reduction from 3SAT to Independent Set, what ensures that no contradictory variable assignments are made?

Answer 71

Adding edges between vertices representing a variable and its negation

Question 72

The number of different ways to prove an 'if and only if' relationship is:

Answer 72

4

Question 73

True or False: In the reduction from 3SAT to Subset Sum, the transformation creates O(nm) numbers.

Answer 73

True

Question 74

Which of the following problems would be best to reduce from when proving Vertex Cover is NP-Complete?

Answer 74

Independent Set

Question 75

In the context of NP-Completeness, what does a subgraph need to satisfy compared to an induced subgraph?

Answer 75

A subgraph can omit edges between its vertices that exist in the original graph

Question 76

True or False: In the reduction from Independent Set to Clique, isolated vertices become connected to all other vertices in the complement graph.

Answer 76

True ## Footnote 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.

Question 77

Which is NOT a valid statement about NP-Completeness?

Answer 77

If a problem is NP-Complete, there must be no polynomial time algorithm for it

Question 78

In SAT, literals within a clause are connected by which operator?

Answer 78

OR (∨)

Question 79

True or False: The Clique problem restricted to graphs where every vertex has degree at most 3 is in P.

Answer 79

True ## Footnote DPV shows it can be solved checking all combinations of 3 vertices

Question 80

When reducing from a known NP-Complete problem A to an unknown problem B, what is the correct statement about their relative hardness?

Answer 80

B is at least as hard as A

Question 81

In the reduction from 3SAT to Subset Sum, what happens if a clause has no satisfied literals?

Answer 81

The corresponding digit cannot sum to the target value

Question 82

For the Vertex Cover problem, what is search component

Answer 82

Finding a vertex cover **at most** budget b

Question 83

In the reduction from Clique to Kite, what structure is added to the original graph?

Answer 83

A path connected to each vertex

Question 84

True or False: Cook-Levin theorem established that SAT is NP-Complete.

Answer 84

True

Question 85

The NotAllEqual-3SAT problem differs from 3SAT by requiring:

Answer 85

Each clause must have at least one true literal and at least one false literal

Question 86

Which reduction technique is used when transforming an optimization problem to a decision problem?

Answer 86

Adding a budget/goal parameter

Question 87

True or False: In proving a problem is NP-Complete, it's sufficient to show that the known NP-Complete problem reduces to it.

Answer 87

False

Question 88

When a problem has a dynamic programming solution with runtime O(nW), it is:

Answer 88

Pseudo-polynomial, not necessarily polynomial

Question 89

In the context of NP-Completeness, what does 'polynomial' refer to?

Answer 89

Runtime that is polynomial in the input size

Question 90

True or False: Exact-4SAT is NP-Complete.

Answer 90

True

Question 91

If we have a polynomial time algorithm for an NP-Complete problem, what can we conclude?

Answer 91

P = NP

Question 92

In the reduction from Independent Set to Vertex Cover, the runtime of the input transformation is:

Answer 92

O(1) | set b = n - g

Question 93

True or False: Knapsack with inputs given in unary is in P.

Answer 93

True

Question 94

The purpose of 'variable edges' in the 3SAT to Independent Set reduction is:

Answer 94

To prevent selecting both a variable and its negation

Question 95

NP-Hard key fact

Answer 95

NP-Hard problems are at least as hard as any problem in NP

Question 96

True or False: If a problem is in P, it must also be in NP.

Answer 96

True

Question 97

In the reduction from SAT to 3SAT, how many new clauses replace a clause with k literals?

Answer 97

k-2

Question 98

What does the 'completeness' in NP-Complete signify?

Answer 98

The problem is both in NP and NP-Hard

Question 99

True or False: STINGY SAT (finding a satisfying assignment with at most k true variables) is NP-Complete.

Answer 99

True

Question 100

If problem A reduces to problem B and problem B reduces to problem C, what can we conclude?

Answer 100

Problem A reduces to problem C