Chapter 8 Art of the impossible Flashcards
(20 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?
Given a graph and an integer k, determine if there is a k-sized subset where every pair is connected.
Is the clique problem NP-complete?
Yes, it was proven by reduction from SAT.
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?
Whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time.
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.
