7
$\begingroup$

Are there zero-knowledge proofs for every answer to the $P=NP$ question?

For instance, if you have a polynomial-time algorithm of moderate complexity for the graph-coloring problem, then it is easy to prove that you have such an algorithm without revealing the algorithm itself. Are zero-knowledge proofs also possible for other proofs that $NP=P$ or for proofs that $NP\ne P$?

Improve this question
$\endgroup$
10
  • 12
    $\begingroup$ @EsaPulkkinen No, it couldn't. P=NP can be stated as an arithmetical statement, and every arithmetical statement provable in ZFC is provable in ZF. $\endgroup$
    – Wojowu
    Commented Jul 3, 2021 at 11:28
  • 2
    $\begingroup$ @Wojowu, indeed $P=NP$ is $\Sigma_2^0$, as discussed at mathoverflow.net/a/163124/44143. I expect there are general results about zero-knowledge proofs for $\Sigma_2$ and $\Pi_2$ arithmetic statements which can be applied to this. $\endgroup$
    – user44143
    Commented Jul 3, 2021 at 14:05
  • 1
    $\begingroup$ I deleted the tag for proof theory, since zero-knowledge proofs are not proofs in that sense -- they are probabilistically convincing arguments instead. $\endgroup$
    – user44143
    Commented Jul 3, 2021 at 14:10
  • 2
    $\begingroup$ @Wojowu It's well possible you are correct. My intuition on this is based on a straightforward analog, where I identify P with feasible single-threaded processing and NP with feasible multiprocessing (using Cobham's thesis). Then P=NP simply asks if concurrency is necessarily a benefit for efficiency. But such questions depend on the model of computation (~Church-Turing thesis), on how time is measured (for zero knowledge proof would have to agree on this), and on many formal mathematical details, whose description could easily contradict the definition of NP or P. $\endgroup$
    – Esa Pulkkinen
    Commented Jul 3, 2021 at 15:23
  • 1
    $\begingroup$ You should probably post this question on cstheory.stackexchange.com . The question is still somewhat unclear though. $\endgroup$
    – none
    Commented Jul 5, 2021 at 23:21

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .