<p>The <strong>NP</strong>-completeness of the original problem was proved by Manders and Adleman [1] using a reduction from <strong>3-SAT</strong>. Their reduction is <em>parsimonious</em>. Thus, (taking into account that the number of prime factors is upper bounded by the length of the input $n$, while in the M–A reduction, it is at least $n^\epsilon$) your problem is complete for <strong>promise-FewP</strong>. Note that by Valiant–Vazirani, already <strong>promise-UP</strong> is <strong>NP</strong>-hard under randomized polynomial-time reductions, hence the same holds for <strong>promise-FewP</strong>. Thus, the problem is essentially as difficult as <strong>NP</strong>.</p>

<p>EDIT: The answer above assumes that in the question, the unclear phrase “the number of occurrences of $a$” means the number of residues $x&lt;L$ such that $x^2\equiv a$. The OP indicates in a comment below that they rather intended it to mean the <em>total</em> number of residues mod $b$ that square to $a$. In the latter case, the problem is solvable in <strong>promise-ZPP</strong>: using the factorization of $b$, just compute all possible square roots of $a$ modulo $b$ by the usual algorithm (Tonelli–Shanks + Hensel’s lifting + Chinese remainder theorem).</p>

<p><strong>Reference:</strong></p>

<p>[1] Kenneth L. Manders and Leonard M. Adleman, <em>NP-complete
  decision problems for binary quadratics</em>, Journal of Computer and System
  Sciences 16 (1978), no. 2, pp. 168–184.</p>

CC BY-SA 3.0
2018-04-05T13:36:38.257Z
Thanks got it. But shouldn't it be 'at most $n^\epsilon$' (if i understand correctly this is the number of prime factors w.r.t. the length) ?
J.Doe
CC BY-SA 3.0
2018-04-05T14:08:56.407Z
No, at least. (The other inequality is trivial anyway.) I need to establish that a problem whose number of solutions is polynomial in the length of the *input* is translated to an instance of the quadratic problem whose number of solutions is polynomial in the number of *factors*. For this, it is needed that $n$ is at most polynomial in the number of factors, or stated more comprehensibly, that the number of factors is at least polynomial in $n$.
Emil Jeřábek
CC BY-SA 3.0
2018-04-06T14:18:59.033Z
Hi. I did try to understand the class **fewP** but I have a big confusion. Looking at the definition (https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fewp) it says "the number of accepting paths is upper bounded by a polynomial in n, the size of the input." 

In other words, for our problem the promise should be:

1. "the number of **x < L**, that give a quadratic residue $a$ are at most ${pct}^C$".

But, the promise in our problem as we said is:

2. "the number of **x < b**, that give a quadratic residue $a$ are at most ${pct}^C$".
J.Doe
CC BY-SA 3.0
2018-04-06T14:19:09.753Z
1. is **promise-FewNPComplete** I understand. But, how is 2. equivalent to 1? Aren't they both different classes?
J.Doe
CC BY-SA 3.0
2018-04-06T14:32:32.443Z
Well, that’s what you get for not writing the question clearly in the first place. 2 and 1 are completely different problems. 2 is solvable in randomized polynomial time by just computing the list of all square roots in the usual way, and checking if any goes below the bound.
Emil Jeřábek
CC BY-SA 3.0
2018-04-06T14:39:42.360Z
lesson learned. i was struggling with this.
J.Doe
CC BY-SA 3.0
2018-04-05T13:19:46.230Z
2018-04-06T14:42:02.383Z
2018-04-06T14:42:02.383Z
Emil Jeřábek
<p><strong>Given:</strong> 3 positive integers $a, b, L$. 
<strong>Problem:</strong> Is there a positive integer $x &lt; L$ such that $x^2 \equiv \ a (mod\ b)$?  </p>

<p>The above problem is NP Complete (as mentioned in G&amp;J) even if we have the factorization of $b$ given. My query is the following: </p>

<p>Suppose we have a promise/condition imposed that, the number of total occurrences of the residue $a$ is polynomially bounded w.r.t. number of prime factors in $b$, i.e. the number of occurrences of $a$ is always less than ${pct}^C$.</p>

<p>$pct$ = number of Prime factors of $b$ , $C$ = some positive integer constant.</p>

<p>Does this problem still remain NP-Complete or it becomes P time solvable.</p>

<p>Essentially, does the number of times a residue occurs is what makes this problem difficult or it doesn't matter and its just dependent on the number of prime factors in $b$?</p>

CC BY-SA 3.0
2018-04-05T09:05:13.987Z
I can't make heads or tails of the question. What do you mean by the "number of occurrences" of a residue? Where is it supposed to "occur"?
Emil Jeřábek
CC BY-SA 3.0
2018-04-05T09:09:02.990Z
Also, you must have meant $\equiv$ rather than $\not\equiv$. As written, the problem is computationally trivial (the answer is always YES, except for degenerate cases).
Emil Jeřábek
CC BY-SA 3.0
2018-04-05T09:09:43.660Z
Sorry. Would try to clarify. There can be multiple $x$ ($x<b$), such that the quadratic residues of each would be $a$.  The count/number of these $x$ (each of which gives a residue $a$) is what I meant by 'number of occurrences'. Thanks corrected that.
J.Doe
<cc.complexity-theory>
Clarification regarding Bounded Quadratic Congruence Problem
J.Doe
# Clarification regarding Bounded Quadratic Congruence Problem

(Asked by: username_0 on 2018-04-05)

**Given:** 3 positive integers $a, b, L$.
**Problem:** Is there a positive integer $x < L$ such that $x^2 \equiv \ a (mod\ b)$?

The above problem is NP Complete (as mentioned in G&J) even if we have the factorization of $b$ given. My query is the following:

Suppose we have a promise/condition imposed that, the number of total occurrences of the residue $a$ is polynomially bounded w.r.t. number of prime factors in $b$, i.e. the number of occurrences of $a$ is always less than ${pct}^C$.

$pct$ = number of Prime factors of $b$ , $C$ = some positive integer constant.

Does this problem still remain NP-Complete or it becomes P time solvable.

Essentially, does the number of times a residue occurs is what makes this problem difficult or it doesn't matter and its just dependent on the number of prime factors in $b$?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: I can't make heads or tails of the question. What do you mean by the "number of occurrences" of a residue? Where is it supposed to "occur"?  
> **username_1**: Also, you must have meant $\equiv$ rather than $\not\equiv$. As written, the problem is computationally trivial (the answer is always YES, except for degenerate cases).  
> **username_0**: Sorry. Would try to clarify. There can be multiple $x$ ($x<b$), such that the quadratic residues of each would be $a$.  The count/number of these $x$ (each of which gives a residue $a$) is what I meant by 'number of occurrences'. Thanks corrected that.  

---

## 1 answers

### Answer by username_1 on 2018-04-05. Score: 4 | Accepted answer

The **NP**-completeness of the original problem was proved by Manders and Adleman [1] using a reduction from **3-SAT**. Their reduction is *parsimonious*. Thus, (taking into account that the number of prime factors is upper bounded by the length of the input $n$, while in the M–A reduction, it is at least $n^\epsilon$) your problem is complete for **promise-FewP**. Note that by Valiant–Vazirani, already **promise-UP** is **NP**-hard under randomized polynomial-time reductions, hence the same holds for **promise-FewP**. Thus, the problem is essentially as difficult as **NP**.

EDIT: The answer above assumes that in the question, the unclear phrase “the number of occurrences of $a$” means the number of residues $xtotal number of residues mod $b$ that square to $a$. In the latter case, the problem is solvable in **promise-ZPP**: using the factorization of $b$, just compute all possible square roots of $a$ modulo $b$ by the usual algorithm (Tonelli–Shanks + Hensel’s lifting + Chinese remainder theorem).

**Reference:**

[1] Kenneth L. Manders and Leonard M. Adleman, *NP-complete
decision problems for binary quadratics*, Journal of Computer and System
Sciences 16 (1978), no. 2, pp. 168–184.

> **Comments:**
> **username_0**: Thanks got it. But shouldn't it be 'at most $n^\epsilon$' (if i understand correctly this is the number of prime factors w.r.t. the length) ?  
> **username_1**: No, at least. (The other inequality is trivial anyway.) I need to establish that a problem whose number of solutions is polynomial in the length of the *input* is translated to an instance of the quadratic problem whose number of solutions is polynomial in the number of *factors*. For this, it is needed that $n$ is at most polynomial in the number of factors, or stated more comprehensibly, that the number of factors is at least polynomial in $n$.  
> **username_0**: Hi. I did try to understand the class **fewP** but I have a big confusion. Looking at the definition (https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fewp) it says "the number of accepting paths is upper bounded by a polynomial in n, the size of the input."   In other words, for our problem the promise should be:  1. "the number of **x < L**, that give a quadratic residue $a$ are at most ${pct}^C$".  But, the promise in our problem as we said is:  2. "the number of **x < b**, that give a quadratic residue $a$ are at most ${pct}^C$".  
> **username_0**: 1. is **promise-FewNPComplete** I understand. But, how is 2. equivalent to 1? Aren't they both different classes?  
> **username_1**: Well, that’s what you get for not writing the question clearly in the first place. 2 and 1 are completely different problems. 2 is solvable in randomized polynomial time by just computing the list of all square roots in the usual way, and checking if any goes below the bound.  
> **username_0**: lesson learned. i was struggling with this.  

---

