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)

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

1 Answer 1


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.

  • $\begingroup$ I’m not claiming any particular cost limit, since as say it obviously depends on the size of the proof. $\endgroup$ Apr 17, 2018 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.