Timeline for Zero-knowledge proofs for answers to the $P=NP$ question
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 5, 2021 at 23:21 | comment | added | none | You should probably post this question on cstheory.stackexchange.com . The question is still somewhat unclear though. | |
| Jul 4, 2021 at 10:29 | comment | added | none | 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). | |
| Jul 4, 2021 at 7:28 | comment | added | Manfred Weis | @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 | |
| Jul 4, 2021 at 5:09 | comment | added | none | 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. | |
| Jul 3, 2021 at 15:23 | comment | added | Esa Pulkkinen | @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. | |
| Jul 3, 2021 at 15:06 | history | edited | user44143 | CC BY-SA 4.0 |
simplified sentences and hyphenated
|
| Jul 3, 2021 at 14:10 | comment | added | user44143 | I deleted the tag for proof theory, since zero-knowledge proofs are not proofs in that sense -- they are probabilistically convincing arguments instead. | |
| Jul 3, 2021 at 14:08 | history | edited | user44143 |
edited tags
|
|
| Jul 3, 2021 at 14:05 | comment | added | user44143 | @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. | |
| Jul 3, 2021 at 11:28 | comment | added | Wojowu | @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. | |
| Jul 3, 2021 at 8:31 | comment | added | Esa Pulkkinen | See kialo.com/p--np-15955 for some references. | |
| Jul 3, 2021 at 8:09 | comment | added | Esa Pulkkinen | 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. | |
| Jul 3, 2021 at 7:12 | history | asked | Manfred Weis | CC BY-SA 4.0 |