Hello, I need to solve this problem for data structures and algorithm design lesson. I am waiting for your helps
Prove that the decision problem POLPOS defined below is NP-Complete by using the nowledge we 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. Furthermore, as this is not a difficult homework, the style and clarity of your steps are necessarily part of the grading. If you write ambiguous or short-cut text you may lose significant 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 p(x1,x2,,xn)- ak0 + akjxi |where aki are integers and m is a positive integer Examples to illustrate the POLPOS problem An instance of POLPOS problem is could be p(x1,x2, x3)-(2 + x1-2%)(-1 + 2x1-3x2 + x3)(3-5X2 + 2x3) In English text is it possible to make (2-x1 + 3x1)(1 + x1 + 4x2 + 3x3) positive by a proper 0 or 1 assignments to the arguments of p? (In this case, the answer is yes because p(1,0,1) >0) Another instance of POLPOS could be: In English text: is it possible to make (1+x1 -x2)(-2x1 X2) positive by a proper 0 or 1 assignment to the arguments of p? (In this case, the answer is no, because no assignment of 0/1 to x1, X2 can make p positive. Try it!) Prove that the decision problem POLPOS defined below is NP-Complete by using the nowledge we 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. Furthermore, as this is not a difficult homework, the style and clarity of your steps are necessarily part of the grading. If you write ambiguous or short-cut text you may lose significant 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 p(x1,x2,,xn)- ak0 + akjxi |where aki are integers and m is a positive integer Examples to illustrate the POLPOS problem An instance of POLPOS problem is could be p(x1,x2, x3)-(2 + x1-2%)(-1 + 2x1-3x2 + x3)(3-5X2 + 2x3) In English text is it possible to make (2-x1 + 3x1)(1 + x1 + 4x2 + 3x3) positive by a proper 0 or 1 assignments to the arguments of p? (In this case, the answer is yes because p(1,0,1) >0) Another instance of POLPOS could be: In English text: is it possible to make (1+x1 -x2)(-2x1 X2) positive by a proper 0 or 1 assignment to the arguments of p? (In this case, the answer is no, because no assignment of 0/1 to x1, X2 can make p positive. Try it!)
