-1
$\begingroup$

If there is someone can prove that the problem "is P equals to NP?" is a NP-COMPLETE problem, what we can conclude from this?

$\endgroup$

migrated from cstheory.stackexchange.com Sep 22 '12 at 19:13

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 8
    $\begingroup$ @TesterNP "Is P = NP" is not a problem for which NP-completeness applies (it's not a parametrized problem in terms of a variable input size) $\endgroup$ – Suresh Sep 21 '12 at 19:13
  • 1
    $\begingroup$ testerNP, P vs NP can indeed be formulated as a question about the halting of a Turing machine that verifies that no other Turing machines solve NP complete problems in P time. but phrased in this way its a question about halting of a TM, but not a decision problem that is proven an algorithm can solve. in other words its basically provably not a decision problem. however a way to evaluate the complexity of the P vs NP problem has been sketched out in a famous paper by Razborov & Rudich called "natural proofs" $\endgroup$ – vzn Sep 22 '12 at 20:01
  • 8
    $\begingroup$ The decision problem: "Given $x$, $P =^? NP$" is in $P$ (time complexity $O(1)$) though we still don't know how to build the 3-states ($q_0,q_Y,q_N$) $TM$ that correctly decides it :-) :-) $\endgroup$ – Vor Sep 22 '12 at 22:02
  • 1
    $\begingroup$ @Vor I think we know exactly what either alternative looks like, we just don't know which is the right one. In any case, I think you should make this an answer. $\endgroup$ – Raphael Sep 23 '12 at 14:13
  • $\begingroup$ wikipedia on P vs NP. see also lance fortnows excellent recent ACM survey, status of the P vs NP problem from 2009. (& can this be put in the FAQ?) $\endgroup$ – vzn Sep 27 '12 at 1:32
4
$\begingroup$

"$\mathsf{P}$ vs. $\mathsf{NP}$" is not a computational problem that depends on an input, we don't have any input on which the computation will depends on, therefore the complexity does not make much sense. The complexity of a computational problem is defined w.r.t. an input that varies (e.g. we will need more time to solve the problem for larger inputs).

For any problem that does not depend on a varying input there exists a trivial algorithm that solves the problem in unit time: either the algorithm that always outputs YES solves the problem or the algorithm that always outputs NO solves it. We may not know which one, but what we know or don't know is irrelevant, what is important is the existence of an algorithm running in constant time solving the problem. In short, any computational problem with no varying input is computationally trivial.

We can think of this question as an instance of a computational problem like "given a first order formula $\varphi$ in the language of arithmetic, is $\varphi$ true?". However it does not make sense to say a problem instance is $\mathsf{NP\text{-}complete}$, complexity theory concepts like $\mathsf{NP\text{-}complete}$ness are defined for languages which are sets of instances. A language containing a single instance is trivial from computational perspective.

$\endgroup$
  • 1
    $\begingroup$ Note that the infamous "$\pi$-problem" relates to a similar (arguably the same) misconception. $\endgroup$ – Raphael Sep 26 '12 at 10:55
  • $\begingroup$ I am afraid that you mixed up terminology. You claimed that P vs NP is not a “computational problem instance” (whatever it means), and then you argued “for any such problem instance…,” which seems contradictory because you had claimed that it is not a problem instance. I think that you meant to write something along “‘P vs NP’ is not a language” in the first paragraph. $\endgroup$ – Tsuyoshi Ito Sep 26 '12 at 20:44
  • $\begingroup$ Yes, I think that the issue which I pointed out has been fixed. $\endgroup$ – Tsuyoshi Ito Sep 26 '12 at 21:16
2
$\begingroup$

While Kaveh's answer is perfectly satisfactory and complete, I can direct you to the following survey article: On P vs NP and Geometric Complexity Theory by K.D. Mulmuley, in which he gives an overview of the "flip theorem" which seems to be a rigorous formulation of the idea "what does P vs NP have to say about it's own provability?".

Informally the theorem states (as far as I understand) that if certain well-believed conjectures in complexity theory are true, then P$\neq$NP only if there is a certain procedure to construct "obstructions" to circuits of size polynomial in $n$ that claim solve the SAT problems of a certain size $n$. Here an obstruction for a given circuit $C$ is essentially an input $S$ such that $C$ gives the wrong answer for input $S$. The theorem further states that these obstructions are "small" in the sense that they can be coded in logarithmic number of bits in $n$, which make it easy to find such obstructions in P time.

The theorem is stated and proven in this article by the same author.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy