Hello

I need help for this question...

Prove that the decision problem POLPOS defined below is NP-Complete by using the knowledge we covered in the class. 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: Zn)-?(@g02@gis)whereaki areintegersandmisapos poi, X2, ak.o+ akixi where aki are integers and mis a positive integer k-1 An instance of POLPOS problem is could be: p(xi, x2, x3) -(2 +x1 - 2x3)(12x1 - 3x2 + x3) In English text: is it possible to make (2 -xi + 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(xi,x2)- (1 +x1 - x2)(-2+x1 + x2) In English text: is it possible to make (1 xi - x2)(-2 +x1 +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 xi, x2 can make p positive. Try it Prove that the decision problem POLPOS defined below is NP-Complete by using the knowledge we covered in the class. 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: Zn)-?(@g02@gis)whereaki areintegersandmisapos poi, X2, ak.o+ akixi where aki are integers and mis a positive integer k-1 An instance of POLPOS problem is could be: p(xi, x2, x3) -(2 +x1 - 2x3)(12x1 - 3x2 + x3) In English text: is it possible to make (2 -xi + 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(xi,x2)- (1 +x1 - x2)(-2+x1 + x2) In English text: is it possible to make (1 xi - x2)(-2 +x1 +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 xi, x2 can make p positive. Try it