<p>Manders and Adleman proved that the following decision problem is NP-complete:</p>

<blockquote>
  <p>Given integers $a,b,c&gt;0$, does the quadratic equation $ax^2+by-c=0$ have a solution in integers $x,y&gt;0$?</p>
</blockquote>

<p>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&gt;0$, does there exist an integer $0\le x&lt;d$ such that $x^2\equiv c\pmod b$?</p>

<p>My question is, what is the complexity of the following problem?</p>

<blockquote>
  <p>Given integers $b,c&gt;0$, does the equation $x^2-cx+by=0$ have a solution in integers $x,y&gt;0$?</p>
</blockquote>

<p>Does the problem become easier if the prime factorization of $b$ is given?</p>

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

<p>The problem is equivalent to: given $b,c&gt;0$, does there exist $0&lt;x&lt;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$.</p>

CC BY-SA 3.0
2017-02-21T18:52:40.167Z
$x^2-cx+by=0\iff (x-(c/2))^2 + by -(c/4)^2=0$.
Turbo
CC BY-SA 3.0
2017-02-22T06:26:20.030Z
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?
TheoryQuest1
CC BY-SA 3.0
2017-02-23T09:25:45.457Z
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.
Emil Jeřábek
CC BY-SA 3.0
2017-02-23T13:45:54.430Z
I have taken the liberty to reformulate the question, in the hopes that it will help its reopening.
Emil Jeřábek
CC BY-SA 3.0
2017-02-25T11:18:00.070Z
@EmilJeřábek Much thanks for the rephrasing.
TheoryQuest1
CC BY-SA 3.0
2017-02-25T11:18:05.093Z
If possible, any comments on how to approach it from those who suggested it is somewhat straightforward ?
TheoryQuest1
<cc.complexity-theory><ds.algorithms>
Worst-case computational complexity of solving Diophantine equation
TheoryQuest1
# Worst-case computational complexity of solving Diophantine equation

(Asked by: username_0 on 2017-02-21)

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

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

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: $x^2-cx+by=0\iff (x-(c/2))^2 + by -(c/4)^2=0$.  
> **username_0**: 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?  
> **username_2**: 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.  
> **username_2**: I have taken the liberty to reformulate the question, in the hopes that it will help its reopening.  
> **username_0**: @EmilJeřábek Much thanks for the rephrasing.  
> **username_0**: If possible, any comments on how to approach it from those who suggested it is somewhat straightforward ?  

---

## 0 answers

