Homework 12
Last updated: Mon, 12 Dec 2022 15:39:20 -0500
Out: Tue Dec 13, 00:00 EST Due: Mon Dec 19, 23:59 EST
This assignment explores the NP class of languages and NP-Complete problems.
Homework Problems
A Way To Prove P = NP? (5 points)
Subset-Sum Problem (12 points)
Knapsack Problem (12 points)
Is NP closed under ...? (5 + 5 = 10 points)
README (1 point)
Total: 40 points
Submitting
Submit your solution to this assignment in Gradescope hw12. Please assign each page to the correct problem and make sure your solutions are legible.
A submission must also include a README containing the required information.
1 A Way To Prove P = NP?
Prove that if the Crossword Puzzle Algorithm Problem from Homework 11 is \textbf{NP}\textrm{-Complete}, then \textbf{P}=\textbf{NP}.
2 Subset-Sum Problem
Prove that the \textit{SUBSET-SUM} problem is \textbf{NP}\textrm{-Complete}.
It must explicitly include the 3 steps for proving NP-Completeness given in class.
Also, the mapping reducibility part must explicitly state the 4 steps given in class.
Finally, the reverse direction of the if-and-only-if of mapping reducibility must prove the contrapositive statement.
HINT: A proof is described in Sipser Theorem 7.56.
NOTE: This problem is testing to see if you are able to read a proof, understand it, and then re-explain it in your own words. So simply submitting a copy (or isomorphic version) of a proof from a textbook or website will not be sufficient.
3 Knapsack Problem
The Knapsack Problem is something that RPG game video gamers solve every time they manage their inventory.
Formally, define the general problem to be a language of triples \left\langle I,wgt_{max},val_{min}\right\rangle where:
I is a set of (wgt,val) pairs representing a set of "items", where each item has a "weight" and a "value",
wgt_{max} is a number representing a maximum "weight",
val_{min} is another number representing a minimum desired "value", and
for some \left\{(w_1,v_1),\ldots,(w_k,v_k)\right\}\subseteq I, \Sigma_{i=1}^k w_i \leq wgt_{max} and \Sigma_{i=1}^k v_i \geq val_{min}.
Prove that the Knapsack Problem is \textbf{NP}\textrm{-Complete}.
HINT: Reduce from one of the known \textbf{NP}\textrm{-Complete} problems we studied in class or this HW.
4 Is NP closed under ...?
Prove that the \mathrm{OP3} operation in Homework 7’s Closed Operations For Regular Languages, One Last Time problem is closed for \textbf{NP} languages.
More specifically:Give the If-Then statement that must be proved.
Prove the statement by giving a table of Statements and Justifications, where the last statement is the If-Then statement to be proved from above.
Now consider whether the \mathrm{OP2} operation in Homework 3’s Practice: Proving An Operation Closed For Regular Languages problem is closed for \textbf{NP} languages.
More specifically:Give the If-Then statement that must be proved.
Explain how the statement might be proved, but also comment on why the statement might not be true.
For example, a correct answer might have a Statements and Justifications table with missing or incomplete steps. It would then comment on why filling in those missing part might be difficult.
HINT: Be wary when using non-deterministic Turing machines (NTMs) in this problem. In particular, NTMs can branch at each step (and every path can accept or reject), but it cannot do anything after that. In other words, it cannot wait for all the branches to halt, and then do more computation. This means that NTMs cannot be called from other NTMs in the same way as deterministic machines.
Concretely, this is not a valid NTM:
call another NTM T on string w
do something with the result