subjects learned in class: 3-sat reduces,sat, polynomial time reduction, ham cyc
ID: 3838566 • Letter: S
Question
subjects learned in class: 3-sat reduces,sat, polynomial time reduction, ham cycle, colorability, vertex cover, set cover, np completeness
Prove that the decision problem the defined below is NP-Complete by using the knowledge we covered in the class using NOTE: Note that this is not an exam question, so you have be precise and clear in what you write, and follow all requirements for a proper proof If you write ambiguous text you may not get any points. POLPOS: Given the n-variable polynomial function p, is there any 0/1 assignment to the arguments x1,x2, ,xn such that p(x1,x2, xn) 0 where p is defined as follows xn) ak o k,i ti where aki are integers and miss a positive integer k-1 An instance of POLPOS problem is could be: p(x1,x2, x3 (2 x1 2x300-1 2x 3x2 x3) In English text: is it possible to make (2 -x1 3x1)(1 x1 4x2 3x3) positive by a proper 0 or 1 assignment to the arguments of p In this case, the answer is yes because p(1,0,1) 0) Another instance of POLPOS could be: p(x1,x2) (1 xi x2)(-2 x1 x2) In English text: is it possible to make (1 x x2)(-2 +x1 x2) positive by a proper 0 or l assignment to the arguments of p? (In this case, the answer is no, because no assignment of 0/1 toxi, x2 can make p positive. Try it!)Explanation / Answer
Np completeness :
The indirect way. Show that there is an NP-hard problem P and a polynomial-time computable function f with the following property: for any instance x of P, f(x) is an instance of TP and it is a "yes" instance of TP if, and only if, p is a "yes" instance of P
. This is how just about every other NP-hard problem, apart from the two listed above, was proven NP-hard.
The indirect way works through a chain of reductions. We need to establish that every problem in NP can be reduced to TP. So, we start with our nondeterministic polynomial-time Turing machine M
and its input x. We convert that to an instance of Boolean satisfiability. Then we convert that into, say, an instance of 3-SAT. Then we convert that into, say, an instance of 3-colourability. Then maybe we convert that into an instance of P
and, finally, convert that into an instance of our fictional problem TP. Because all of these reductions work for every instance of the problem, we have a reduction from our generic NP problem to TP.
Both in theory and in practice, that is how reductions are done: you need to translate every instance of the problem. But we don't actually need that much. Look at the first step of the chain of reductions in the previous paragraph. We started with any Turing machine at all, and we converted it into a Boolean formula. Without looking closer, all we know is that we've produced some Boolean formula, and we don't know any details about it. However, looking more closely at the reduction, we see that the formula is in conjunctive normal form (CNF) (or that the proof can easily be modified to make it so). For the next step, converting to 3-CNF, the definition of reductions tells us that we have to be able to translate every Boolean formula into one in 3-CNF, but we know we don't need to do that much. It would suffice to translate only the formulas that are already in conjunctive normal form, because those are the only ones that the translation from Turing machines will produce. And that's actually what the standard proof does.
Normally, when a new problem is proven NP-hard, a full reduction is given from some known NP-hard problem to the new problem, which translates all instances. However, in principal, you could get away with a reduction that does less than that, as long as it covers enough instances to establish the chain back to the generic Turing machine M
and its input x. To give another example, 3-colourability is NP-hard because of a standard reduction from 3-SAT. You could prove a new problem to be NP-hard by a reduction that only translates the instances of 3-colourability that could be produced by that reduction from 3-SAT. This works because 3-colourability is already NP-hard when its input is restricted to be from the class of graphs that can arise from the reduction from 3-SAT.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.