2
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ 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"? $\endgroup$ – Emil Jeřábek Apr 5 '18 at 9:05
  • $\begingroup$ 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). $\endgroup$ – Emil Jeřábek Apr 5 '18 at 9:09
  • $\begingroup$ 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. $\endgroup$ – J.Doe Apr 5 '18 at 9:09
4
$\begingroup$

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 $x<L$ such that $x^2\equiv a$. The OP indicates in a comment below that they rather intended it to mean the total 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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) ? $\endgroup$ – J.Doe Apr 5 '18 at 13:36
  • 1
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Apr 5 '18 at 14:08
  • $\begingroup$ Hi. I did try to understand the class fewP but I have a big confusion. Looking at the definition (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$". $\endgroup$ – J.Doe Apr 6 '18 at 14:18
  • $\begingroup$ 1. is promise-FewNPComplete I understand. But, how is 2. equivalent to 1? Aren't they both different classes? $\endgroup$ – J.Doe Apr 6 '18 at 14:19
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 6 '18 at 14:32

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.