Unit 14: More on Intractable Problems - Practice Quiz

1 Which optimization problem is a well-known example of an NP-hard problem?

2 What does it mean for a problem to be NP-hard?

3 Which statement about NP-hard problems is correct?

4 Which version of the Knapsack Problem is generally NP-hard?

5 Which problem asks for a shortest tour that visits every city exactly once and returns to the start?

6 Which problem was the first problem proved to be NP-complete?

7 A problem is NP-complete when it is:

8 Which graph problem is a well-known NP-complete decision problem?

9 What does the Clique decision problem ask?

10 Which problem asks whether some numbers in a set add up to a specified target?

11 What is the main conclusion of Cook's theorem?

12 Cook's theorem is primarily associated with which complexity class?

13 According to Cook's theorem, every problem in NP can be reduced in polynomial time to:

14 Who is Cook's theorem named after?

15 Why is Cook's theorem historically important?

16 What is the main purpose of a problem reduction?

17 To prove that a new problem is NP-hard, which reduction direction is normally used?

18 What does mean?

19 If and can be solved in polynomial time, what follows?

20 What must be efficient in a polynomial-time reduction?

21 Which version of the Traveling Salesperson Problem (TSP) is commonly classified as NP-hard?

22 Why can an undecidable problem, such as the Halting Problem, be described as NP-hard?

23 An algorithm returns the size of a maximum clique in a graph. Why is this task NP-hard?

24 Suppose a polynomial-time algorithm computes an optimal solution to every instance of an NP-hard optimization problem. What would follow for its associated NP-complete decision problem?

25 Which statement correctly distinguishes an NP-hard problem from an NP-complete problem?

26 For the decision version of CLIQUE, what serves as a polynomially verifiable certificate for a yes-instance?

27 Which formulation of Vertex Cover is NP-complete?

28 A SUBSET-SUM instance contains integers and target . Which certificate proves that it is a yes-instance?

29 Which additional fact is needed, beyond proving that a problem is NP-hard, to classify it as NP-complete?

30 A graph problem asks whether a simple cycle visits every vertex exactly once. Which NP-complete problem is being described?

31 What is the central conclusion of Cook's theorem?

32 In the proof of Cook's theorem, what does the constructed Boolean formula primarily encode?

33 Why is the SAT problem itself in NP?

34 If SAT were shown to have a polynomial-time algorithm, what consequence would Cook's theorem imply?

35 Which property ensures that the formula constructed in Cook's theorem has polynomial size?

36 Suppose and has a polynomial-time algorithm. What can be concluded about ?

37 To prove that a new problem is NP-hard using a known NP-complete problem , which reduction direction is required?

38 A reduction maps each instance of problem to of problem . Which condition must hold for a valid many-one reduction?

39 If and , which conclusion follows from transitivity?

40 A researcher proves , where is NP-complete and is in NP. What classification follows for ?

41 Suppose and are polynomial-time many-one reductions. Which conclusion follows without any additional complexity assumptions?

42 Let be NP-hard and suppose . What is the strongest conclusion that follows solely from these facts?

43 Why is the optimization version of Traveling Salesperson generally called NP-hard rather than NP-complete?

44 Which statement most precisely captures Cook's theorem, also called the Cook–Levin theorem?

45 A nondeterministic Turing machine runs in time . In the standard Cook–Levin tableau construction, why can its computation be represented by a formula of polynomial size?

46 In the Cook–Levin reduction, what corresponds to the nondeterministic choices made by the simulated machine?

47 Assume an oracle returns the exact minimum cost of a TSP tour. How can it decide the threshold version asking whether a tour of cost at most exists?

48 Consider the language . Which classification is correct under polynomial-time many-one reductions?

49 How does changing integer encoding affect the classical SUBSET-SUM decision problem?

50 Which classification correctly describes four common restrictions of Boolean satisfiability?

51 TAUT is coNP-complete. If TAUT were also NP-hard under polynomial-time many-one reductions, what major consequence would follow?

52 Suppose is NP-complete and both and hold. What follows?

53 What would follow if the strongly NP-complete 3-PARTITION problem had an exact pseudo-polynomial-time algorithm?

54 For the decision version of HAMILTONIAN-CYCLE, which certificate and verifier establish membership in NP?

55 Why does the Cook–Levin construction not explicitly enumerate all computation branches of a nondeterministic machine?

56 A proposed reduction from to maps every yes-instance of to a yes-instance of , but some no-instances of also map to yes-instances of . Why is it invalid as a many-one reduction?

57 Why does the fact that a proposed coloring can be checked efficiently not show that computing the chromatic number belongs to NP?

58 Which transformation correctly reduces CLIQUE to VERTEX-COVER for a graph with vertices?

59 In a Cook–Levin tableau, which clauses enforce that a given cell contains exactly one symbol or state marker?

60 Suppose is NP-hard under polynomial-time many-one reductions and via a polynomial-time Turing reduction. What can be concluded directly about ?