7

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

Manfred Weis
  • 12,594
  • 4
  • 34
  • 71
  • There are more possible answers to P=NP problem than is apparent. It's non-trivial to even list every possible answer. P=NP could be dependent on the axiom of choice, for example. – Esa Pulkkinen Jul 03 '21 at 08:09
  • See https://www.kialo.com/p--np-15955 for some references. – Esa Pulkkinen Jul 03 '21 at 08:31
  • 12
    @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. – Wojowu Jul 03 '21 at 11:28
  • 2
    @Wojowu, indeed $P=NP$ is $\Sigma_2^0$, as discussed at https://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. –  Jul 03 '21 at 14:05
  • 1
    I deleted the tag for proof theory, since zero-knowledge proofs are not proofs in that sense -- they are probabilistically convincing arguments instead. –  Jul 03 '21 at 14:10
  • 2
    @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. – Esa Pulkkinen Jul 03 '21 at 15:23
  • You could have a P-time algorithm for SAT with no proof that it is actually P-time. In fact, if such an algorithm exists, Levin's Universal Search is an instance of it. ZKP doesn't really come into play here since even if you know that your algorithm is P-time, you might have no idea what the exponent or constant multiplier is. E.g. they could be unimaginably large. – none Jul 04 '21 at 05:09
  • @none my restriction on polynomial time algorithms with moderate exponent when proving knowledge of an efficient solution to an NP complete problem was on purpose to allow for checking that the yes/no outcome for the decision variant or the optimal solution are predicted correctly in 100% of the cases and the time between receiving a test instance and providing the correct answer grows according to the claimed constant exponent. Efficient algorithms with sky-rocketing exponents wouldn't impact anyone's life except for the person that found the proof becoming a millionaire – Manfred Weis Jul 04 '21 at 07:28
  • The exponent could be small (like 2 or 3) while the multiplicative constant could be unthinkably large. Something like that happens in the Robertson-Seymour graph minor theorem. This theorem implies that for any given graph G, there is a cubic-time algorithm to find whether an arbitrary graph has G as a minor, but it gives no idea what the algorithm is, and the algorithm could be different for every G (note the order of the quantifiers). – none Jul 04 '21 at 10:29
  • 1
    You should probably post this question on https://cstheory.stackexchange.com/ . The question is still somewhat unclear though. – none Jul 05 '21 at 23:21

0 Answers0