3
$\begingroup$

It is well known that if $n!$ cannot be computed in $\mathsf{polylog}(n)$ ring ($\Bbb Z$) operations, then $\mathsf P\neq\mathsf{NP}$ in $\mathsf{BSS}$ model.

Suppose if we assume $\mathsf P=\mathsf{NP}$ in $\mathsf{BSS}$ model (and hence in Turing model), is there an hypothetical procedure that can be explictly written out that would compute $n!$ in $\mathsf{polylog}(n)$ ring ($\Bbb Z$) operations?

Improve this question
$\endgroup$
12
  • $\begingroup$ Does it matter that $n!$ can be computed in subexponential time? For SAT this would mean collapse AFAICT. $\endgroup$
    – joro
    Commented Jul 31, 2015 at 12:22
  • $\begingroup$ Why would $n!$ in subexp time collapse $\mathsf{SAT}$? Is there a direct connection between $n!$ and $\mathsf{SAT}$? $\endgroup$
    – Turbo
    Commented Jul 31, 2015 at 12:32
  • $\begingroup$ I know that $\mathsf{permanent}$ is easy implies $n!$ is easy. I do not know of connection to $\mathsf{SAT}$. $\endgroup$
    – Turbo
    Commented Jul 31, 2015 at 12:46
  • $\begingroup$ No, I don't claim subexp n! implies SAT collapse. Just asking if it implies something else, since subexp results are not trivial. I meant subexp SAT would imply SAT collapse. $\endgroup$
    – joro
    Commented Jul 31, 2015 at 12:59
  • $\begingroup$ What does phrase 'subexp SAT would imply SAT collapse' imply? $\endgroup$
    – Turbo
    Commented Jul 31, 2015 at 13:01

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .