4
$\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)

Improve this question
$\endgroup$
6
  • 9
    $\begingroup$ She or he will have enough trouble convincing the world without trying to hide this information. $\endgroup$
    – Thomas Steinke
    Commented May 10, 2017 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
    Commented May 11, 2017 at 9:34
  • 2
    $\begingroup$ A straightforward application of zero-knowledge proofs should do the trick. $\endgroup$
    – Or Meir
    Commented 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$
    – ghosts_in_the_code
    Commented 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
    Commented May 12, 2017 at 17:10

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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