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 '17 at 17:29
  • 1
    $\begingroup$ @Thomas Really? I thought a properly written proof shouldn't be too hard to accept. $\endgroup$ – ghosts_in_the_code May 11 '17 at 9:34
  • 2
    $\begingroup$ A straightforward application of zero-knowledge proofs should do the trick. $\endgroup$ – Or Meir May 11 '17 at 22:33
  • 1
    $\begingroup$ @OrMeir So what exactly will the zero knowledge proof be; that's what I'm asking $\endgroup$ – ghosts_in_the_code May 12 '17 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 '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.

| cite | improve this answer | |
  • $\begingroup$ I’m not claiming any particular cost limit, since as say it obviously depends on the size of the proof. $\endgroup$ – Geoffrey Irving Apr 17 '18 at 2:29

Your Answer

