12

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?

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152
  • 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. – Kaveh Oct 17 '10 at 15:46
  • 1
    [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. – Kaveh Oct 17 '10 at 15:49
  • 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. – Kaveh Oct 17 '10 at 15:59
  • @Kaveh: Clarification added. – Sadeq Dousti Oct 17 '10 at 18:35
  • 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. – vzn Nov 02 '13 at 01:29

2 Answers2

20

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!

Dana Moshkovitz
  • 10,979
  • 1
  • 50
  • 77
9

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.

Alexey Romanov
  • 551
  • 2
  • 8
  • 2
    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). – Sadeq Dousti Oct 17 '10 at 13:09
  • 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. – Alexey Romanov Oct 17 '10 at 15:11
  • 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. – Daniel Apon Oct 17 '10 at 16:14
  • [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? – Daniel Apon Oct 17 '10 at 16:15
  • @Daniel Apron: In classical mathematics (not constructive mathematics) we can't do better, there exists an algorithm, there exists a look-up table, we don't need to be able to tell what is the algorithm, we don't need to know the table. The existence is sufficient. – Kaveh Oct 17 '10 at 16:21
  • @Kaveh, I'm not sure I follow. Could you clarify which piece of my statement you're objecting to? (Sorry :)) – Daniel Apon Oct 17 '10 at 16:26
  • @Daniel Apron: Sorry, :) This part: "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." – Kaveh Oct 17 '10 at 16:32
  • @Kaveh: Another way to word my objection is that the claim above isn't actually arguing that L is in DTIME(O(1)); rather, I believe it argues that, with access to an NP oracle, membership in L can be computed in DTIME(O(1)). Hence, it's not arguing L is in P, but rather that L is in P^NP. To claim L is P by the above argument misses the point that you've "cheated" by querying an implicit oracle. – Daniel Apon Oct 17 '10 at 16:40
  • I mean, otherwise, "P = NP" can be decided to be part of an always true language or an always false language in constant time, and he should write this up very quickly! – Daniel Apon Oct 17 '10 at 16:57
  • @Daniel Apron: I understood it as saying that this is just one instance, it does not make much sense to talk about its complexity. Complexity is w.r.t. input, what is the input here? If there is no input, then it is a constant function. (But of course we don't know which of the two constant function it is. I can give you two trivial algorithms and prove (in classical mathematics) that at least one of them is correctly solving "Does $P \neq NP$ have a proof in ZFC?" (similarly $P=NP$), but if you ask me which one, I will say I don't know, I only know one of them is solving it. ) – Kaveh Oct 17 '10 at 17:17
  • Let me explain my point with another example: given a graph G and a number k, does G have a k-clique? This is NP-complete. But as soon as we fix G, then it is very easy in theory, although G can be so large that in practice we might not be able to find the largest k such that G has a k-clique, but we don't need to find one to say that the problem is very easy after fixing G. – Kaveh Oct 17 '10 at 17:26
  • 1
    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)$. – Sadeq Dousti Oct 17 '10 at 18:32
  • @Kaveh: I agree; I was making the assumption that "P = NP" (resp. "P $\ne$ NP") is a member of some language that includes an infinitely long list of different theorems (part of the trouble is that the question asks about the specific definition of this language, L, which isn't well-defined yet!). The complexity of L, then, is not asking about a fixed theorem! It appears Sadeq has clarified this point already though... (P.S. It's Apon, not Apron! ;)) – Daniel Apon Oct 17 '10 at 19:02
  • @Daniel Apon: Sorry for misspelling your last name. :) – Kaveh Oct 17 '10 at 19:45