12
$\begingroup$

The following question uses ideas from cryptography applied to complexity theory. That said, it is a purely complexity-theoretic question, and no crypto knowledge whatsoever is required to answer it.

I deliberately write this question very informally. Lacking details, it is possibly stated a bit incorrectly. Please feel free to point out the corrections in your answers.

In the following papaper:
Nonmalleable Cryptography, Danny Dolev, Cynthia Dwork, and Moni Naor, SIAM Rev. 45, 727 (2003), DOI:10.1137/S0036144503429856,
the authors write:

Suppose researcher A has obtained a proof that P ≠ NP and wishes to communicate this fact to professor B. Suppose that, to protect herself, A proves her claim to B in a zero-knowledge fashion...

There are several standard NP-complete problems, like satisfiability (SAT), Graph-Hamiltonicity, and Graph-3-Colorability (G3C), for which zero-knowledge proofs exist. The standard way of proving any NP-theorem is to first reduce it to an instance of the aforementioned NP-complete problems, and then conduct the zero-knowledge proof.

This question pertains to such reduction. Assume that the P vs. NP is settled in any of the following ways:

  • P = NP
  • P ≠ NP
  • P vs. NP is independent of the standard axiomatic set theory.

Let σ denote the proof. Then, P vs. NP is in an NP language (since there exists a short proof for it). The reduction from the theorem (say, P ≠ NP) to the NP-complete problem (say SAT) is independent of σ. That is:

There exists a formula ϕ which is satisfiable if and only if P ≠ NP.

This is well beyond my imagination! It seems that, even if we are given the proof σ, it is unlikely that we can construct such formula ϕ.

Could anyone shed some light on this?

In addition, let L be an NP language in which P vs. NP lies. The language is consists of infinitely many theorems like P vs. NP, of arbitrary sizes.

What is a candidate for L?
Can L be NP-complete?

Improve this question
$\endgroup$
5
  • $\begingroup$ I don't get this part: "Let σ denote the proof. Then, P vs. NP is in NP (since there exists a short proof for it). The reduction from the theorem (say, P ≠ NP) to the NP-complete problem (say SAT) is independent of σ. That is: There exists a formula ϕ which is satisfiable if and only if P ≠ NP.". Could you please explain it a little more? It doesn't make sense to me that "P vs NP is in NP", even if you change it to "is there a proof of length at most n in theory T for P \neq NP". Either there is a smallest n such there is a proof of that size for the question or there is no such proof. $\endgroup$
    – Kaveh
    Commented Oct 17, 2010 at 15:46
  • 1
    $\begingroup$ [continued] If there is none the function that always rejects is answering the question, and in the other case the function that accepts any number larger than the length of smallest proof and rejects anything less than it will solve the question. The question that given $\varphi$, and $n$, does $\varphi$ has a proof of size n in $T$ is NP, but if you fix $\varphi$ it does not make much sense. $\endgroup$
    – Kaveh
    Commented Oct 17, 2010 at 15:49
  • $\begingroup$ Also note that the question that "given a statement $\varphi$ (like $P \neq NP$), is it provable in a first-order theory $T$?" is not decidable in general. $\endgroup$
    – Kaveh
    Commented Oct 17, 2010 at 15:59
  • $\begingroup$ @Kaveh: Clarification added. $\endgroup$
    – Sadeq Dousti
    Commented Oct 17, 2010 at 18:35
  • $\begingroup$ some interesting ideas but it makes no sense to say a "proof is in NP" or that "there exists a short proof". ie there could be some method of making those parallels but it would have to be more formally defined. the closest to these ideas, it seems, would be razborov/rudich natural proofs framework. $\endgroup$
    – vzn
    Commented Nov 2, 2013 at 1:29

2 Answers 2

Reset to default
20
$\begingroup$

The way to view testing a math statement (e.g., a resolution of P vs NP) as a question of the form "is formula .. satisfiable" is the following:

Fix some axiom system. Given a string of length n, whether the string is a proof for the math statement in the axiom system, is something one can define in a straightforward manner: the string should consist of propositions. Each proposition should either be an axiom, or should follow from the previous propositions by one of the inference rules.

It's not a problem to define a Boolean formula that verifies all this. All you should know is the length n of the proof!

Improve this answer
$\endgroup$
9
$\begingroup$

P vs. NP is in NP (since there exists a short proof for it)

That doesn't make much sense to me. NP is a complexity class for decision problems which have arbitrarily large instances, and P vs. NP doesn't have them. From what you say later:

let L be an NP language in which P vs. NP lies.

you may instead mean that P vs. NP is an instance of an NP problem; but of course it is! It is also instance of an infinite number of P, DTIME(n), etc. problems. In particular, here are two DTIME(1) candidates for L, precisely one of which is correct: always return true; or always return false.

Improve this answer
$\endgroup$
14
  • 2
    $\begingroup$ Please read the side note at the beginning of the question again. I was putting this informally, and that leads to your confusion. To formalize, one must consider a generalization of the "P vs. NP" theorem. For infinitely many n, the generalization assumes a theorem of length n. The theorems give rise to a language L, which cannot be possibly decided in DTIME(1). $\endgroup$
    – Sadeq Dousti
    Commented Oct 17, 2010 at 13:09
  • $\begingroup$ Then a short proof/disproof of "P vs. NP" is only one instance of "generalized P vs. NP" (perhaps an easy one?), and it doesn't follow that GPvNP is in NP. $\endgroup$
    – Alexey Romanov
    Commented Oct 17, 2010 at 15:11
  • $\begingroup$ Downvoted: I understand the objection to the way the first quoted statement is worded, since members of NP are sets and "P vs. NP" is not a set. However, on the second objection, any "NP problem" is a decision problem that can always be legitimately formulated as deciding whether a string is in a language; I don't see anything wrong with his definition of L. Further, the appeal to trivial, always-true or always-false DTIME(1) languages ignores the point: If we already know ALL true statements, presumably we build a look-up table for the Turing machine to access to constant time. $\endgroup$
    – Daniel Apon
    Commented Oct 17, 2010 at 16:14
  • $\begingroup$ [Cont'd] But assuming L is a proper language (i.e. an infinite set), then you're assuming an infinitely large table of "true statements" to access, which seems to break all kinds of rules. Or more to the point: Why doesn't your argument for DTIME(1) generalize to ANY language, not just the odd one we're considering now? $\endgroup$
    – Daniel Apon
    Commented Oct 17, 2010 at 16:15
  • 1
    $\begingroup$ Thanks everyone. Please note that, one of the questions I asked was about some language L in which "P vs. NP" fits. That is, "P vs. NP" is just an instance of such language. The language generalizes the instance to infinitely many theorems. It does is highly unlikely $L \in DTIME(1)$. $\endgroup$
    – Sadeq Dousti
    Commented Oct 17, 2010 at 18:32

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.