1
$\begingroup$

I found a statement that $ax^2+by-c=0$ is NP Complete. However I am unable to find any document showing the proof.

There is a paper on few pay-walled sites but they are out of reach for me. The document is NP-complete decision problems for quadratic polynomials by Manders and Adleman, and one copy is here : http://dl.acm.org/citation.cfm?id=803627

The formal statement of the problem is : Given positive integers $a, b, c \ge 0$, find positive integers $x, y \ge 0$ such that $ax^2+by-c=0$. I am also unable to figure out how a 3SAT problem might be reduced to this form.

If someone can explain or guide me to a tutorial or explanation for this online it would be great.

Thanks!

$\endgroup$
1
  • $\begingroup$ I just realised I hadn't put up the full problem statement. My bad. I have edited the problem to correct this. Hope this clarifies what I am looking for. $\endgroup$ – gautam Aug 13 '15 at 17:40
1
$\begingroup$

Page 150 of The Nature of Computation by Moore and Mertens has it; it's a reduction from Subset Sum.

$\endgroup$
1
  • $\begingroup$ Thanks a ton! This is great. $\endgroup$ – gautam Aug 14 '15 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.