<p>Or Meir’s comment is almost but not quite right, since it would be satisfied by a proof that P vs. NP is not independent even if the prover didn’t know which. A corrected version is “X is either the hash of a proof that P = NP or the hash of a proof that P $\ne$ NP”, where hash is SHA256, say.  Running that statement through a zero knowledge proof system gives the desired evidence.</p>

<p>However, if I was given such a proof, I would assign higher probability to someone having found a bug in the logical system being used.  It would be quite difficult to surmount that qualification in practice, since bugs in proof systems are fairly common.</p>

CC BY-SA 3.0
2018-04-17T02:29:23.640Z
I’m not claiming any particular cost limit, since as say it obviously depends on the size of the proof.
Geoffrey Irving
CC BY-SA 3.0
2018-04-13T15:35:15.297Z
2018-04-13T16:29:07.973Z
2018-04-13T16:29:07.973Z
Geoffrey Irving
<p>Suppose a person has proved that P≠NP. He wants to let the world know that he has solved the P versus NP problem but does not want to reveal that he has proved P≠NP as opposed to P=NP. </p>

<p>Is there any purely theoretical way to do so?</p>

<p>Also any practical evidence he can show to back his claim? (I'm not sure it this part is on-topic)</p>

CC BY-SA 3.0
2017-05-10T17:29:15.060Z
She or he will have enough trouble convincing the world without trying to hide this information.
Thomas Steinke
CC BY-SA 3.0
2017-05-11T09:34:30.467Z
@Thomas Really? I thought a properly written proof shouldn't be too hard to accept.
ghosts_in_the_code
CC BY-SA 3.0
2017-05-11T22:33:48.240Z
A straightforward application of zero-knowledge proofs should do the trick.
Or Meir
CC BY-SA 3.0
2017-05-12T11:09:28.683Z
@OrMeir So what exactly will the zero knowledge proof be; that's what I'm asking
ghosts_in_the_code
CC BY-SA 3.0
2017-05-12T17:10:11.757Z
The NP statement would be "there exists a proof for P = NP or a proof for P \ne NP". A witness for this statement can be verified in polynomial time, so it is indeed in NP. Now apply zero-knowledge proof to this statement.
Or Meir
CC BY-SA 3.0
2017-05-12T17:14:38.803Z
Let boolean cct  A be the verifier of s and cct B the verifier of Not(s) [ the ccts have the same input size chosen by the prover who obviously has a satisfying string for one cct]. Create cct C = A or B ;  and use the 'garbled cct'  ' (https://crypto.stackexchange.com/a/37993/42746) protocol to convince the second party that you do indeed have a satisfying assignment for  C.
ARi
<p-vs-np>
Can one prove the discovery of a P versus NP solution without actually revealing it?
ghosts_in_the_code
# Can one prove the discovery of a P versus NP solution without actually revealing it?

(Asked by: username_0 on 2017-05-10)

Suppose a person has proved that P≠NP. He wants to let the world know that he has solved the P versus NP problem but does not want to reveal that he has proved P≠NP as opposed to P=NP.

Is there any purely theoretical way to do so?

Also any practical evidence he can show to back his claim? (I'm not sure it this part is on-topic)

**Tags:** p-vs-np

> **Comments:**
> **username_1**: She or he will have enough trouble convincing the world without trying to hide this information.  
> **username_0**: @Thomas Really? I thought a properly written proof shouldn't be too hard to accept.  
> **username_2**: A straightforward application of zero-knowledge proofs should do the trick.  
> **username_0**: @OrMeir So what exactly will the zero knowledge proof be; that's what I'm asking  
> **username_2**: The NP statement would be "there exists a proof for P = NP or a proof for P \ne NP". A witness for this statement can be verified in polynomial time, so it is indeed in NP. Now apply zero-knowledge proof to this statement.  
> **username_3**: Let boolean cct  A be the verifier of s and cct B the verifier of Not(s) [ the ccts have the same input size chosen by the prover who obviously has a satisfying string for one cct]. Create cct C = A or B ;  and use the 'garbled cct'  ' (https://crypto.stackexchange.com/a/37993/42746) protocol to convince the second party that you do indeed have a satisfying assignment for  C.  

---

## 1 answers

### Answer by username_4 on 2018-04-13. Score: 3

username_2’s comment is almost but not quite right, since it would be satisfied by a proof that P vs. NP is not independent even if the prover didn’t know which. A corrected version is “X is either the hash of a proof that P = NP or the hash of a proof that P $\ne$ NP”, where hash is SHA256, say. Running that statement through a zero knowledge proof system gives the desired evidence.

However, if I was given such a proof, I would assign higher probability to someone having found a bug in the logical system being used. It would be quite difficult to surmount that qualification in practice, since bugs in proof systems are fairly common.

> **Comments:**
> **username_4**: I’m not claiming any particular cost limit, since as say it obviously depends on the size of the proof.  

---

