Consider the problem of PARTITION: we are given a set of numbers (if you prefer, you...

 

Transcribed Image Text:

Consider the problem of PARTITION: we are given a set of numbers (if you prefer, you may think of these as positive integers; however, that is not necessarily part of the problem statement). We want to answer the boolean question: is there a subset of these elements whose sum is exactly half of the total? Note: you may wish to wait on part (d), and possibly part (c), until we have covered NP- complete as a topic in lecture. (a) Express this as a language recognition problem. (b) Prove that your language from the previous part is in NP. (c) Observe that we could decide this language by making a call to Subset Sum's decider (1/2)x. Why does this not prove anything about the difficulty with parameter of this problem? = (d) Prove that this problem is NP-complete. Consider the problem of PARTITION: we are given a set of numbers (if you prefer, you may think of these as positive integers; however, that is not necessarily part of the problem statement). We want to answer the boolean question: is there a subset of these elements whose sum is exactly half of the total? Note: you may wish to wait on part (d), and possibly part (c), until we have covered NP- complete as a topic in lecture. (a) Express this as a language recognition problem. (b) Prove that your language from the previous part is in NP. (c) Observe that we could decide this language by making a call to Subset Sum's decider (1/2)x. Why does this not prove anything about the difficulty with parameter of this problem? = (d) Prove that this problem is NP-complete.