<blockquote>
  <p>P vs. NP is in NP (since there exists a short proof for it)</p>
</blockquote>

<p>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:</p>

<blockquote>
  <p>let L be an NP language in which P vs. NP lies.</p>
</blockquote>

<p>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 <code>true</code>; or always return <code>false</code>.</p>

CC BY-SA 2.5
2010-10-17T13:09:38.427Z
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
CC BY-SA 2.5
2010-10-17T15:11:03.590Z
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
CC BY-SA 2.5
2010-10-17T16:14:24.250Z
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
CC BY-SA 2.5
2010-10-17T16:15:39.377Z
[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
CC BY-SA 2.5
2010-10-17T16:21:09.300Z
@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
CC BY-SA 2.5
2010-10-17T16:26:53.570Z
@Kaveh, I'm not sure I follow. Could you clarify which piece of my statement you're objecting to? (Sorry :))
Daniel Apon
CC BY-SA 2.5
2010-10-17T16:32:21.663Z
@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
CC BY-SA 2.5
2010-10-17T16:40:12.983Z
@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
CC BY-SA 2.5
2010-10-17T16:57:11.963Z
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
CC BY-SA 2.5
2010-10-17T17:17:55.380Z
@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
CC BY-SA 2.5
2010-10-17T17:26:43.757Z
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
CC BY-SA 2.5
2010-10-17T18:32:14.670Z
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
CC BY-SA 2.5
2010-10-17T19:02:04.710Z
@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
CC BY-SA 2.5
2010-10-17T19:45:15.847Z
@Daniel Apon: Sorry for misspelling your last name. :)
Kaveh
CC BY-SA 2.5
2010-10-17T12:39:39.187Z
2010-10-17T12:39:39.187Z
Alexey Romanov
<p>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:</p>

<p>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.</p>

<p>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!</p>

CC BY-SA 2.5
2010-10-17T11:49:42.673Z
2010-10-17T11:49:42.673Z
Dana Moshkovitz
<p>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.</p>

<p>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.</p>

<hr>

<p>In the following papaper:<br/>
<a href="http://link.aip.org/link/SIREAD/v45/i4/p727/s1">Nonmalleable Cryptography, Danny Dolev, Cynthia Dwork, and Moni Naor, SIAM Rev. 45, 727 (2003), DOI:10.1137/S0036144503429856</a>,<br/>
the authors write:</p>

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

<p>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.</p>

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

<ul>
<li>P = NP</li>
<li>P ≠ NP</li>
<li>P vs. NP is independent of the standard axiomatic set theory.</li>
</ul>

<p>Let σ denote the proof. Then, <strong>P vs. NP</strong> is in an <strong>NP</strong> 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:</p>

<p><code>There exists a formula ϕ which is satisfiable if and only if P ≠ NP.</code></p>

<p>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 ϕ.</p>

<blockquote>
  <p>Could anyone shed some light on this?</p>
</blockquote>

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

<blockquote>
  <p>What is a candidate for L? <br/>
  Can L be NP-complete?</p>
</blockquote>

CC BY-SA 3.0
2013-11-02T01:29:52.043Z
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
CC BY-SA 2.5
2010-10-17T15:46:01.127Z
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
CC BY-SA 2.5
2010-10-17T15:49:36.077Z
[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
CC BY-SA 2.5
2010-10-17T15:59:38.667Z
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
CC BY-SA 2.5
2010-10-17T18:35:36.457Z
@Kaveh: Clarification added.
Sadeq Dousti
<cc.complexity-theory><complexity-classes><np-hardness><p-vs-np>
Reducing P vs. NP to SAT
Sadeq Dousti
# Reducing P vs. NP to SAT

(Asked by: username_0 on 2010-10-17)

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](http://link.aip.org/link/SIREAD/v45/i4/p727/s1),  
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?

**Tags:** cc.complexity-theory, complexity-classes, np-hardness, p-vs-np
> **Comments:**
> **username_2**: 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.  
> **username_2**: [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.  
> **username_2**: 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.  
> **username_0**: @Kaveh: Clarification added.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_5 on 2010-10-17. Score: 20 | Accepted answer

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!


---

### Answer by username_3 on 2010-10-17. Score: 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`.

> **Comments:**
> **username_0**: 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).  
> **username_3**: 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.  
> **username_4**: 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.  
> **username_4**: [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?  
> **username_2**: @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.  
> **username_4**: @Kaveh, I'm not sure I follow. Could you clarify which piece of my statement you're objecting to? (Sorry :))  
> **username_2**: @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."  
> **username_4**: @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.  
> **username_4**: 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!  
> **username_2**: @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. )  
> **username_2**: 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.  
> **username_0**: 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)$.  
> **username_4**: @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! ;))  
> **username_2**: @Daniel Apon: Sorry for misspelling your last name. :)  

---

