# Can one prove the discovery of a P versus NP solution without actually revealing it?

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)

• She or he will have enough trouble convincing the world without trying to hide this information. – Thomas May 10 '17 at 17:29
• @Thomas Really? I thought a properly written proof shouldn't be too hard to accept. – ghosts_in_the_code May 11 '17 at 9:34
• A straightforward application of zero-knowledge proofs should do the trick. – Or Meir May 11 '17 at 22:33
• @OrMeir So what exactly will the zero knowledge proof be; that's what I'm asking – ghosts_in_the_code May 12 '17 at 11:09
• 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 May 12 '17 at 17:10

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.

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.

• I’m not claiming any particular cost limit, since as say it obviously depends on the size of the proof. – Geoffrey Irving Apr 17 '18 at 2:29