6
$\begingroup$

Manders and Adleman proved that the following decision problem is NP-complete:

Given integers $a,b,c>0$, does the quadratic equation $ax^2+by-c=0$ have a solution in integers $x,y>0$?

The problem remains NP-complete even if the prime factorization of $b$ is given, and $a=1$. It is equivalent to the following problem: given integers $b,c,d>0$, does there exist an integer $0\le x<d$ such that $x^2\equiv c\pmod b$?

My question is, what is the complexity of the following problem?

Given integers $b,c>0$, does the equation $x^2-cx+by=0$ have a solution in integers $x,y>0$?

Does the problem become easier if the prime factorization of $b$ is given?

Note that any solution has $x,y$ bounded by $c$, hence the problem is clearly in NP.

The problem is equivalent to: given $b,c>0$, does there exist $0<x<c$ such that $x^2-cx\equiv0\pmod b$? Notice that even if we know the factorization of $b$, the number of solutions of this quadratic equation modulo $b$ is exponential in the number of prime factors of $b$ by the Chinese remainder theorem, hence it is not clear how to check whether some of them falls in the target range. For example, in the case where $b$ is odd and coprime to $c$, an $x$ solves the equation iff $x\equiv0$ or $x\equiv c\pmod{p^e}$ for every prime power $p^e$ that divides $b$.

$\endgroup$
  • 4
    $\begingroup$ $x^2-cx+by=0\iff (x-(c/2))^2 + by -(c/4)^2=0$. $\endgroup$ – Turbo Feb 21 '17 at 18:52
  • $\begingroup$ Much thanks. Edited to clarify it as worst case. I am aware that we can solve the prime case in Polynomial Time easily. But the composite case, where the solution has to be positive (given the factorization of b) is the case i am struggling with. It seems we can use the Chinese Remainder Theorem in Polynomial Time in general, but the additional (x>0, y>0) is troubling for such an algorithm? $\endgroup$ – TheoryQuest1 Feb 22 '17 at 6:26
  • 4
    $\begingroup$ While the question could be formulated better, the meaning is reasonably clear, and it seems rather nontrivial to me. I thus don't understand all the harsh votes. I'm voting to reopen. $\endgroup$ – Emil Jeřábek Feb 23 '17 at 9:25
  • 1
    $\begingroup$ I have taken the liberty to reformulate the question, in the hopes that it will help its reopening. $\endgroup$ – Emil Jeřábek Feb 23 '17 at 13:45
  • $\begingroup$ @EmilJeřábek Much thanks for the rephrasing. $\endgroup$ – TheoryQuest1 Feb 25 '17 at 11:18

Your Answer

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

Browse other questions tagged or ask your own question.