Chapter 8 Art of the impossible Flashcards
(25 cards)
What is a tractable problem?
A problem solvable by an algorithm with polynomial time complexity.
What does intractable mean in computational complexity?
Problems where it is impossible to guarantee finding an exact solution in polynomial time.
Why are polynomial-time algorithms favored?
Because they are closed under addition/multiplication and typically efficient in practice.
What is the class P?
Set of decision problems solvable in polynomial time.
What is the class NP?
Set of decision problems where a ‘yes’ answer can be verified in polynomial time.
What is NP-completeness?
A problem is NP-complete if it’s in NP and all other NP problems can be polynomially reduced to it.
What does it mean if a problem is NP-hard?
It’s at least as hard as the hardest problems in NP, but not necessarily in NP itself.
What is the SAT problem?
Determining if a CNF formula has a satisfying assignment.
Who proved SAT is NP-complete?
Stephen Cook.
What is the clique problem?
A subset of vertices such that every pair of vertices in the subset is directly connected by an edge. Given an undirected graph
Is the clique problem NP-complete?
Yes, it was proven by reduction from SAT. It is NP-Complete if it is in NP (can verify a solution quickly) and it is NP-hard (at least as hard as any problem in NP)
What is a decision problem?
A problem with a yes/no answer.
Why is reduction important?
It helps relate problem complexities by transforming one problem into another.
What does the P = NP question ask?
The P = NP question asks whether every problem for which a solution can be verified in polynomial time can also be solved in polynomial time.(The P = NP question asks whether every problem whose solution can be verified in polynomial time (i.e., in NP) can also be solved in polynomial time (i.e., is in P).)
What is the importance of NP-complete problems?
Solving any NP-complete problem in polynomial time would solve all problems in NP.
What is the Hamiltonian Circuit Problem (HCP)?
Deciding whether a graph contains a tour visiting each vertex exactly once.
How can HCP be used in TSP approximation arguments?
By constructing a TSP instance from an HCP input to test approximation algorithm limits.
Can all problems be approximated efficiently?
No, some approximations (like for TSP) are themselves NP-complete.
What is an uncomputable problem?
A problem for which no algorithm exists to solve it.
What is conjunctive normal form (CNF)?
A logical formula composed of ANDs of ORs over Boolean variables.
What is Reduction
Transforming any instance of the first problem into an instance of a second problem so if we solve the second problem we can get a solution for the first. this mapping of I -> I’ takes polynomial time
Approximation loss as a multiplicative factor(
multiplicative approximation guarantee, which is a common and formal way to define how good an approximate solution is compared to the optimal one.
s* is the optimal solution cost
s is the cost of an approximate solution
We say that the solution s has an approximation factor of r if
s/s* <= r
If r is closer to 1 the better the approximation
The cost of the approimate solution is at most r times worse than the optimal
What are phase transitions (link to SAT)?
A phase transition in SAT refers to a sudden change in satisfiability as the number of clauses increases relative to variables.
For 3-SAT, this happens around a ratio of
𝑚/𝑛≈4.26
m/n≈4.26, where problems shift from mostly solvable to mostly unsolvable — and also become hardest to solve.
Black-box reduction
Given some input I to a problem A, transform I into some I’ which is an instance of Problem B.
Choose an algorithm B alg which can solve Problem B with input I’ and returns true/false accordingly.
Reduced Problem A to Problem B if B alg returns true for input I’ if an only if the solution for problem A is true at I, for all values of I (hence if mapping I to I’ takes polynomial time then the reduction takes polynomial time)
