1. What is the relation between NP-complete and NP-hard?
Correct Answer: A. Every NP-complete problem is NP-hard
Explanation: NP-complete problems are a subset of NP-hard problems with an additional constraint: 1) NP-complete: A problem is in NP AND all problems in NP reduce to it in polynomial time 2) NP-hard: Any problem to which all problems in NP can be reduced in polynomial time Therefore, every NP-complete problem is NP-hard, but the reverse is not true. Some NP-hard problems are not in NP at all (e.g., the halting problem).
2. If P = NP, then:
Correct Answer: B. All NP-complete problems become easy
Explanation: If P = NP, then: - All problems in NP (including NP-complete problems) would be solvable in polynomial time - Problems previously thought to be intractable would have efficient algorithms - This would revolutionize fields like cryptography, which rely on certain problems being hard "Easy" in computational complexity means solvable in polynomial time. Currently, we only know exponential-time algorithms for NP-complete problems.
3. Which of the following is not NP-hard?
Correct Answer: D. Linear Search
Explanation: - Clique Problem: Finding if a graph has a clique of size k is NP-complete - Subset Sum: Determining if a subset of numbers sums to a target value is NP-complete - TSP (Decision): Deciding if a tour exists with cost ≤ k is NP-complete Linear Search is in P - it has a time complexity of O(n) and can be solved efficiently. It doesn't have the hardness characteristic of NP-hard problems.
4. Which of the following is true for an NP-hard problem?
Correct Answer: C. All NP problems reduce to it
Explanation: By definition, NP-hard problems are those to which every problem in NP can be reduced in polynomial time. This means: - An NP-hard problem is at least as hard as the hardest problems in NP - It may or may not be in NP itself (unlike NP-complete problems) - It's not necessarily easier or harder than NP-complete - The number of solutions varies by problem instance
5. The term "reduction" in NP-completeness means:
Correct Answer: C. Transforming one problem to another in polynomial time
Explanation: In complexity theory, a reduction is a transformation from one problem to another such that: 1) The transformation itself takes polynomial time 2) The original problem has a solution if and only if the transformed problem has a solution Reductions are used to show NP-completeness by demonstrating that if we could solve the target problem efficiently, we could also solve a known NP-complete problem efficiently.
6. Cook's Theorem states that:
Correct Answer: B. SAT is NP-complete
Explanation: Cook's Theorem (1971) was a major breakthrough in computational complexity theory: - It proved that the Boolean Satisfiability Problem (SAT) is NP-complete - SAT was the first problem proven to be NP-complete - After this theorem, other problems could be shown to be NP-complete by reducing SAT to them This theorem opened the door to proving many problems NP-complete through reduction chains starting from SAT.
7. Which is not a characteristic of NP-complete problems?
Correct Answer: B. Polynomial-time solvability
Explanation: NP-complete problems have the following characteristics: 1) They are in NP (solutions can be verified in polynomial time) 2) All problems in NP reduce to them in polynomial time 3) They are believed NOT to be solvable in polynomial time (if they were, P would equal NP) Polynomial-time solvability is precisely what we don't know about NP-complete problems. If they were known to be polynomial-time solvable, P would equal NP.
8. What does it mean if a problem is in P ∩ NP?
Correct Answer: B. It belongs to both P and NP
Explanation: P ∩ NP is the intersection of classes P and NP: - P consists of problems solvable in polynomial time - NP consists of problems verifiable in polynomial time - P ∩ NP means problems that are both solvable AND verifiable in polynomial time Actually, P ⊆ NP, so P ∩ NP = P. All problems in P are also in NP (we can verify solutions by re-solving the problem).
9. What is the best-known algorithm for solving an NP-complete problem?
Correct Answer: B. Exponential-time brute force
Explanation: For NP-complete problems: - We don't know of any polynomial-time algorithms - The best-known algorithms run in exponential time - We often use techniques like branch-and-bound, dynamic programming, etc., to mitigate exponential growth While heuristics and approximation algorithms exist for many NP-complete problems, they don't guarantee optimal solutions. For guaranteed optimal solutions, we generally need exponential-time algorithms.
10. Which of the following statements is true?
Correct Answer: B. If one NP-complete problem has a polynomial-time algorithm, then P = NP
Explanation: This is a fundamental property of NP-complete problems: - All NP-complete problems are polynomially reducible to each other - If any one NP-complete problem has a polynomial-time solution, then ALL NP-complete problems would have polynomial-time solutions - This would mean that P = NP, solving one of the most important open questions in computer science No such polynomial-time algorithm for any NP-complete problem has been discovered, despite decades of research.