3
$\begingroup$

Is the following promise problem in $\mathsf{NP}$ or $\mathsf{coNP}$ or even in $\mathsf{PH}$? $$\Pi:\mathsf{Given}\mbox{ }p,a,s\in\Bbb N,\mbox{ }\mathsf{with}\mbox{ }p\mbox{ }\mathsf{a}\mbox{ }\mathsf{prime}\mbox{ }\mathsf{such}\mbox{ }\mathsf{that}\mbox{ }s<p,\mbox{ }a<p,\mbox{ }\mathsf{is }\mbox{ }0< a!\bmod p < s?$$

$$\mathsf{Conjecture}:\Pi\in\mathsf{PSPACE}\backslash\mathsf{PH}$$

Improve this question
$\endgroup$
8
  • $\begingroup$ NP with respect to what? $a$? Or the total number of bits of the data? $\endgroup$
    – Per Alexandersson
    Commented Aug 29, 2015 at 17:56
  • $\begingroup$ I guess it is the total number of bits (which is basically $\log n$ unless $a$ is very large, which would only help us). The problem is that the obvious algorithm takes about $a$ steps (each of which involves arithmetic in Z/nZ). $\endgroup$
    – Boris Bukh
    Commented Aug 29, 2015 at 17:58
  • $\begingroup$ @BorisBukh Yes you are right. Total bits is correct measure. If $a>n$, $a!\bmod n=0$. If $n<s$, then $a!\bmod n<s$ always holds as well. So relevant range is $0<a,s<n$. $\endgroup$
    – user76479
    Commented Aug 29, 2015 at 18:08
  • 3
    $\begingroup$ @Arul Word of advice: include some motivation/discussions in your questions. Your questions are good, but they take much thinking to appreciate, which is why they do not get nearly as much attention as they deserve. $\endgroup$
    – Boris Bukh
    Commented Aug 29, 2015 at 18:18
  • 2
    $\begingroup$ The problem is in CH by scaling up the uniform TC^0 algorithms for iterated multiplication and integral division due to Hesse, Allender, and Barrington. I don’t see how to make it into PH. $\endgroup$
    – Emil Jeřábek
    Commented Sep 23, 2015 at 11:39

0

Reset to default

You must log in to answer this question.