NP Hardness Flashcards
What is NP-hardness?
NP-hardness refers to the classification of decision problems which are at least as hard as the hardest problems in NP. If an NP-hard problem can be solved in polynomial time, then all problems in NP can also be solved in polynomial time.
What is the difference between P, NP, and NP-hard?
P is the class of problems solvable in polynomial time. NP is the class of problems verifiable in polynomial time. NP-hard problems may not be in NP but are as difficult as any problem in NP; they are the hardest problems in terms of computational complexity.
What does it mean if a problem is NP-complete?
A problem is NP-complete if it is in NP and as hard as any problem in NP. Solving any NP-complete problem quickly (in polynomial time) would allow all NP problems to be quickly solvable.
How do approximation algorithms relate to NP-hard problems?
Approximation algorithms provide near-optimal solutions to NP-hard problems in polynomial time, often with a known error margin or approximation ratio, making them practical despite the intractability of the exact solution.
What are meta-heuristics and how are they used in solving NP-hard problems?
Meta-heuristics are strategies that guide the search process towards optimal solutions by exploring and exploiting the solution space using methods like genetic algorithms, simulated annealing, and ant colony optimization. They are particularly useful for complex NP-hard problems.
What is a computationally tractable problem?
A problem is considered computationally tractable if it can be solved in polynomial time, which generally means the problem is in class P.
How can decision and optimization problems be related in computational complexity?
Every optimization problem has an associated decision problem that sets a threshold for the solution’s value. If the decision version is tractable, then the optimization problem is usually also considered tractable.
Why are decision problems significant in theoretical computer science?
Decision problems help in understanding the computational complexity of problems. They are central in classifying problems into complexity classes like P, NP, and others.
How are formal languages related to decision problems?
Decision problems can be represented as formal languages where each “yes” instance of a problem corresponds to a string in the language. This equivalence helps in applying theories from formal languages to computational problems.
What does it mean for a problem to be in the complexity class NP?
A problem is in class NP if there exists a polynomial-time verifier. A verifier can check whether a given solution to the problem is correct, also in polynomial time, based on some provided proof or witness.
