# Please help understand how $ax^2+by-c=0$ is NP Complete

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!

• 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. – gautam Aug 13 '15 at 17:40

## 1 Answer

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

• Thanks a ton! This is great. – gautam Aug 14 '15 at 6:24