Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Software Engineering > P, NP, NP-Completeness, NP-Hardness, Undecidability > Flashcards

P, NP, NP-Completeness, NP-Hardness, Undecidability Flashcards

1
Q

Are all P problems NP?

A

Yes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is NP?

A

Problems for which solutions can be verified in polynomial time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

If a problem is in NP, and can’t be proven to be P, what do we say about it?

A

It’s not known to be P.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is P?

A

NP problems that have polynomial time solutions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is polynomial time?

A

Complexity that varies entirely as a function of the input size.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the significance of P=NP?

A

It would mean all algorithms with polynomial time verification (NP) can also be solved in polynomial time (P), which would be huge.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is NP-Hard?

A

Problems with no known polynomial solutions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How are the difficulties of NP-Hard and NP problems related?

A

An NP-Hard problem is at least as hard as the hardest NP problems.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How are NP-Hard and NP related?

A

NP-Hard problems can be in NP, but also can be outside NP. If outside NP, we can’t verify it in polynomial time. The hardest NP problems are also NP-Hard.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How do you prove that a problem is NP-Complete?

A
  1. Prove it’s in NP by showing that it has a polynomial time verification
  2. Prove it’s NP-Hard by reducing a known-NP-Complete problem to it in polynomial time (inputs and outputs)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What must you cover when proving that an unknown problem is NP-Complete by reducing a known-NP-Complete problem to it?

A
  1. Inputs to the known-NPC can be converted to the unknown problem in polynomial time
  2. Solution to the unknown problem can be converted back to the known-NPC in polynomial time
  3. If there is a solution to the unknown problem, there is a solution to the known-NPC
  4. If there is no solution to the unknown problem, there is no solution to the known-NPC
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How do you prove that a problem is NP-Hard?

A

Prove that a known NP-Hard or NP-Complete problem can be reduced to it. (Does not require proof of being in NP)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How are the difficulty of NP-Complete and NP related?

A

NP-Complete problems are the hardest NP problems.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is Undecidable?

A

No algorithm can solve the problem for every input (but maybe some), even with unlimited time and space.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the Halting Problem?

A

An Undecidable problem built on a contradiction which proves that Undecidable problems exist. It is not possible to solve the Halting Problem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the idea behind the Halting Problem?

A 
Suppose we have an algorithm Terminator(P, I) that solves the Halting Problem for every input. We recursively call it in the Halting Problem to show that it can’t terminate:
Harmful(J):
(1) If Terminator(J, J):
  Goto (1)
Else Return()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

If a problem is P, is it NP, NP-Hard, NP-Complete, Undecidable?

A

NP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

If a problem is NP, is it P, NP-Hard, NP-Complete, Undecidable?

A

None necessarily

19
Q

If a problem is NP-Hard, is it P, NP, NP-Complete, Undecidable?

A

None necessarily

20
Q

If a problem is NP-Complete, is it P, NP, NP-Hard, Undecidable?

A

NP, NP-Hard

21
Q

If a problem is Undecidable, is it P, NP, NP-Hard, NP-Complete?

A

None

22
Q

What are the known NP-Complete problems?

A

SAT, 3SAT, Clique, Independent Set, Vertex Cover, Subset Sum, Knapsack Search, Integer Linear Programming

23
Q

What is the SAT problem?

A

SAT(C)
Complexity: NP-Complete
Input: C is a CNF with any number of variables (n variables) and clauses (m clauses)
Output: assignment of each variable such that the CNF is true

24
Q

What is the 3SAT problem?

A

3SAT(C)
Complexity: NP-Complete
Input: C is a CNF whose clauses have at most 3 literals
Output: assignment of each variable such that the CNF is true

25
Q

What is the Clique problem?

A

Clique(G, k)
Complexity: NP-Complete
Input: G is an undirected, unweighted graph, k is the target size of the clique
Output: A clique with >= k vertices
Background: A clique is a subset of vertices in a graph that are fully connected

26
Q

What is the Independent Set problem?

A

IndependentSet(G, k)
Complexity: NP-Complete
Input: G is an undirected, unweighted graph, k is the target size of the independent set
Output: An independent set with >= k vertices
Background: An independent set is a subset of vertices in a graph that have no edge between any pair of them

27
Q

What is the Vertex Cover problem?

A

VertexCover(G, k)
Complexity: NP-Complete
Input: G is an undirected, unweighted graph. k is the target size of the vertex cover
Output: A vertex cover with >= k vertices
Background: A vertex cover is a subset of vertices in a graph such that all edges in the graph have at least one vertex in the subset

28
Q

What is the Subset Sum problem?

A

SubsetSum(A, t)
Complexity: NP-Complete
Input: A is a list of integers. t is a target sum
Output: A subset of integers from A that add up to t
Background: A DP algorithm exists which solves this problem in O(nt) time

29
Q

What is the Knapsack Search problem?

A

KnapsackSearch(W, V, B, g)
Complexity: NP-Complete
Input: W is the weight of each item, V is the value of each item, B is the capacity of the knapsack, g is the target value
Output: A subset of items with >= g value and <= B weight

30
Q

What is the easiest problem to reduce to 3SAT?

A

SAT

31
Q

What is the easiest problem to reduce to Independent Set?

A

3SAT

32
Q

What is the easiest problem to reduce to Vertex Cover?

A

Independent Set

33
Q

What is the easiest problem to reduce to Clique?

A

Independent Set

34
Q

What is the easiest problem to reduce to Integer Linear Programming?

A

3SAT

35
Q

What is the easiest problem to reduce to Subset Sum?

A

3SAT

36
Q

What is the easiest problem to reduce to Knapsack Search?

A

Subset Sum

37
Q

How do you prove 3SAT is NP-Complete?

A

Reduce SAT to 3SAT by introducing new variables to toggle each clause on or off. Create k-3 new variables as Y1, Y2, Y3, etc.
C’ = (X1 v X2 v Y1) ^ (!Y1 v X3 v Y2) … (!Y{k-4} v X{k-2} v Y{k-3}) ^ (!Y{k-3} v X{k-1} v Xk)

38
Q

How do you prove Independent Set is NP-Complete?

A

Reduce 3SAT to Independent Set by encoding the expression as a graph. Literals for clauses are fully connected, then each X must be connected to each !X and vice versa. g = m because satisfying m clauses takes g independent vertices/variables.

39
Q

How do you prove Clique is NP-Complete?

A

Reduce Independent Set to Clique by taking the complement of the Independent Set graph and running Clique on it.

40
Q

How do you prove Vertex Cover is NP-Complete?

A

Reduce Independent Set to Vertex Cover, but with b=n-g.

41
Q

How do you prove Subset Sum is NP-Complete?

A

Verification takes O(n log t) which is polynomial (log t is a function of input size because it takes that many bits). Reduce 3SAT to Subset Sum by encoding the satisfiability into t and combining variables and clauses. Make a table with 2n+2m+1 rows and n+m columns, fill in which ones are needed.

42
Q

How do you prove that Knapsack Search is NP-Complete?

A

TODO

43
Q

How do you prove Integer Linear Programming is NP-Complete?

A

Reduce Max-SAT to ILP by encoding each literal as true or false assignments, and clauses as summations that must sum up to new z variables. We try to maximize the sum of the z variables.

44
Q

How do you produce a polynomial time approximation of an NP-Hard problem?

A
  1. Reduce to ILP
  2. Relax to LP
  3. Solve the LP (Simplex or other polynomial algorithm)
  4. Round the solution (randomized or other technique)

Software Engineering (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions