2
$\begingroup$

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)

$\endgroup$
  • 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
3
$\begingroup$

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 | |
$\endgroup$
  • $\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

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.