8

How to prove that $P \neq NP$?

To prove that $P = NP$ all we need to do is to solve one NP-Complete problem in polynomial time for any input, and because all the NP-Complete problems have reduction from one to each other we can say $P = NP$.

What would be if I be able to prove that one of the NP-Complete problems cannot be solved in polynomial time. Is there any problem that been proven to be in NP and not in P?

I did not proved for any problem that it belongs only to NP and not to P, I am just asking in general.

Edit: Some one stated:

If you could prove that there existed an NP-Complete problem that cannot be solved in P, then it would imply that $P \neq NP$

I want to comment about it here. If you have problem $A$ that could be solved by polynomial reduction to problem $B$, you can say that $A$ is not harder than $B$. If you be able to solve $B$ in polynomial time, it will also apply to $A$, how ever it's the lower bounds. If you be able to prove that $B$ cannot be solved in polynomial time, it doe's not prove that $A$ cannot be solved in polynomial time. A good example for that is 2-sat problem that could be reduced to 3-sat. 2-sat has polynomial solution, we did not found any polynomial solution for 3-sat yet.

Ilya Gazman
  • 1,440
  • “To prove that P=NP all we need to do is to solve one NP-Complete problem in polynomial time for any input” is not only not right, it isn't even wrong. A single instance of any problem, NP-complete or not, can always be solved in constant time. – MJD Dec 02 '13 at 14:32
  • @MJD I don't understand you can you please explain yourself in more details. – Ilya Gazman Dec 02 '13 at 14:34
  • 1
    @MJD it's not true. Solving one NP-complete problem in P time and space, means finding an algorithm that solves the whole problem, not one instance. – rewritten Dec 02 '13 at 15:19
  • 2
    I see now that the scope of "for any input" is unclear. I took it to mean "for any single input". – MJD Dec 02 '13 at 15:34
  • its called lower bounds not "bottom bounds" – vzn Dec 02 '13 at 17:36

5 Answers5

9

What would be if I be able to prove that one of the NP-Complete problems cannot be solved in polynomial time.

I assume you mean "problems cannot be solved in polynomial time on a deterministic Turing machine". NP, after all, stands for "nondeterministic polynomial", and includes the decision problems that can be solved in polynomial time on a nondeterministic Turing machine.

What would be if I be able to prove that one of the NP-Complete problems cannot be solved in polynomial time [on a deterministic Turing machine].

Then you would prove that all the $\rm NP\text{-}complete$ problems have no deterministic polynomial-time algorithms.

Proof by contradiction:

  1. Imagine we have some algorithm, $A$, can solve some $\rm NP\text{-}complete$ problem, $S$.
  2. Let us call your "one of the $\rm NP\text{-}complete$ problems" $R$.
  3. Accordingly, $R$ cannot be solved in polynomial time (deterministically); because you have some given proof.
  4. Since they are both $\rm NP\text{-}complete$ problems, then by Cook reductions, we can reduce $R\stackrel{...}{\rightarrow} S$ in polynomial time (deterministically).
  5. Then we can use $A(S)$ and solve $S$. This is a contradiction to $(3)$.

Is there any problem that been proven to be in NP and not in P?

I am not sure what you are actually trying to ask here, but here is a summary on the complexity classes.

$\rm \mathbf P$: is the class of decision problems that can can be solved in polynomial time (deterministically).

There are several equivalent ways of looking at $\rm NP$.

$\rm \mathbf{NP}$:

  • is the class of decision problems that can be solved in polynomial time on a nondeterministic Turing machine.
  • is the class of decision problems for which one can easily verify the solutions of their corresponding optimization problems (which are also proofs of the decision).

The two explanations above are intuitively equivalent: The non-determinism of a NTM can use the verifiability of the answer to "try all solutions" and only keep the one that successfully verifies.

$\rm {NP}$ obviously includes all of $\rm P$.

$\rm \mathbf{NP\text{-}complete}$: is the class of decision problems that are the hardest problems in $\rm NP$. These problems have reductions each-other. Indeed, all of $\rm P$ and $\rm NP$ can be reduced to any $\rm NP\text{-}complete$ problem.

$\rm\mathbf{P}$ vs $\rm\mathbf{NP}$: is the question about whether the $\rm NP\text{-}complete$ class of problems can be solved as fast as the problems in $\rm P$; in other words, does nondeterminism make a machine "faster" (in the sense of polynomial-time=fast, superpolynomial-time=slow).

$\rm\mathbf{NP\text{-}hard}$: are the set of decision problems (some definitions include search and optimization problems) that are at least as hard as $\rm NP\text{-}complete$ problems. So, all $\rm NP\text{-}complete$ are also $\rm NP\text{-}hard$ problems.

A nice picture from wikipedia:

enter image description here

So back to your question:

Is there any problem that been proven to be in NP and not in P?

EDIT: Just to be clear, I understood this to mean:

Is there any problem that been proven to be in NP and [proven] not [to be] in P?

The answer is NO, because that would imply $\rm P\ne NP$. Proof by contradiction:

  1. Imagine $\rm P=NP$
  2. Imagine there is a problem, $R$ that is in $\rm NP$, but not in $\rm P$.
  3. $\rm NP\text{-}complete$ problems are the hardest in $\rm NP$ (all problems in NP can indeed be reduced to any $\rm NP\text{-}complete$ problem).
  4. All $\rm NP\text{-}complete$ problems must be at least as hard as $R$, which follows from $(2,3)$.
  5. All $\rm NP\text{-}complete$ problems are not in $\rm P$, as $R$ is not in $\rm P$, and $\rm NP\text{-}complete$ problems hare harder than $R$ ( from $(2,4)$ ). Therefore $\rm NP \not\in P$, thus $\rm P\ne NP$. This contradicts $(1)$.
Realz Slaw
  • 652
  • I'm not sure that P=NP is actually provable right now. If you say so, it's probably not that easy though. – snowfall512 Dec 02 '13 at 19:39
  • 1
    @user43400 where do I say so? – Realz Slaw Dec 02 '13 at 19:41
  • I'm just saying that what you said, if true, would help prove P=NP shortly. I'm not an expert at P=NP, but I think this won't be solved very soon. – snowfall512 Dec 02 '13 at 19:44
  • 1
    @user43400 what did I say that gave you that idea? – Realz Slaw Dec 02 '13 at 20:09
  • 1
    @user43400 Everything this poster has said here is correct. Perhaps you are confused by his "proof by contradiction," which makes the $P = NP$ problem appear to be deceptively simple? The difficult part is step 3: "Prove R cannot be solved in polynomial time (deterministically)". That's the part that no one's been able to do. – BlueRaja - Danny Pflughoeft Dec 02 '13 at 22:33
  • OH I GET WHAT YOU mean :) – snowfall512 Dec 10 '13 at 21:05
  • Your proof by contradiction is unnecessary long. The question asks if $P$ and $NP$ are the same sets. If some problem is in $NP$ but not in $P$, then they are not the same set, $P\neq NP$, case closed. – Denis Jan 21 '14 at 21:06
  • A small issue with the diagram is that even if P = NP, NP-complete is slightly smaller. It excludes the trivial languages $\varnothing$ and $\Sigma^*$, which cannot be NP-complete or P-complete – Caleb Stanford Jul 20 '18 at 19:07
8

there is some confusion in the question showing a lack of some basic understanding of the theory of NP completeness which is well documented in many places. particularly in this question:

Is there any problem that been proven to be in NP?

yes all NP complete problems are in NP. there are hundreds, maybe thousands of NP complete problems and minor variants. see eg Garey/Johnson, Computers & Intractability, theory of NP completeness

How to prove that P≠NP?

obviously to anyone with even cursory knowledge in the area, this is the Big Open Question that has eluded researchers for over four decades, the short answer is that nobody knows even after serious/intense effort by worlds leading experts. there are many ideas. a few leading ones:

  • circuit theory/complexity. prove that boolean circuits that compute NP complete problems must be "inherently large". some success [ie lower bounds] has been achieved with simpler models eg monotone circuits.
  • GCT is a newer idea using geometry ideas.
  • descriptive complexity. related to the power of proofs. Fagins theorem shows a correspondence with P sets and a specific proof system.
  • etc! many others!
vzn
  • 834
  • 1
    VZN you such a show off. Ofcourse I do not have knowledge in this area, otherwise I wouldn't be asking. – Ilya Gazman Dec 02 '13 at 18:39
  • 1
    B. unf the question(s) show a lack of knowledge documented even on basic wikipedia page(s). RTFM! try reading/understanding it carefully! addendum: a small minority of experts suspect P=?NP could be unprovable, a good survey by aaronson, is P vs NP formally independent?.... – vzn Dec 02 '13 at 19:09
  • 2
    You might want to add to the first part of your answer that all problems that are known to be in P are also known to be in NP. In fact it's not trivial to come up with an example of a decision problem that is not known to be in NP. – MJD Dec 02 '13 at 20:29
  • 1
    @vzn I wish I could give you 331 reputation points (all that I have now) for giving the link of such an interesting paper. I will put a photo of you in my desktop background. – rewritten Dec 02 '13 at 20:38
  • comment: this answer quotes an earlier version of the question, now edited. it is now asking about the existence of lower bounds on NP hard problems. basically no "nontrivial" lower bounds have been proven and if they were its close to the P=?NP question... example of problems that are provably not in NP: there are some known for Expspace by a proof of Meyer/stockmeyer. ("fullness of regular languages with exponentiation.") & by the way, agree the theory is inherently tricky & counterintuitive at times to learn & talk about for neophytes, hence the answer/(tough) encouragement.... – vzn Dec 02 '13 at 22:58
  • In case it should be useful to you in the future, I didn't detect any encouragement, tough or otherwise, in this answer. – Kevin Carlson Dec 03 '13 at 00:02
  • in case it should be useful to you in the future, I regard all answers to questions as ultimately encouraging. myself & others have had long prior conversations with b. in a se CS chat room. anyone interested feel free to join the party. – vzn Dec 03 '13 at 00:17
  • another note, further circumstantial evidence for its sheer difficulty other than its 4 decade unsolved status, P vs NP has a $1M "Millenium prize" unclaimed for over 1 decade. – vzn Dec 05 '13 at 16:19
  • Can you elaborate on "etc! many others!"? I was going to ask the same thing myself, but I found this had already been asked (and answered). – lvella Aug 20 '15 at 02:26
5

If you find a general algorithm that solves a single NP-complete problem in polynomial time, then you will have effectively proved that $P=NP$.

Beware that solving one instance of a specific problem is not enough, you have to give an algorithm which solves any instances of the problem with any input data, and prove that the algorithm is polynomial in the size of the input.

rewritten
  • 3,092
3

If you think about this for a minute, you will see that it's exactly as hard to prove that a given $NP$-complete problem cannot be solved in polynomial time as to prove that $P=NP$. To flesh that out if $P=NP$, then of course there are no $NP$-complete problems that cannot be solved in polynomial time. On the other hand, if there's even a single problem in $NP$ that's not in $P$, regardless of whether it's $NP$-complete, then $P\neq NP$. (Although if there is such a problem there must be an $NP$-complete one.)

I don't quite understand what you mean by second question, "what if I find a special case...?" As to the question after that, there are lots of problems known to be in $NP:$ any problem in $P$, any $NP$-complete problem, etc...The interesting question, which may be what you're driving at, is whether there are any problems known to be in $NP$ but not in $P$. But as the previous paragraph describes, if there were one, then the $P$ versus $NP$ problem would be solved.

Kevin Carlson
  • 52,457
  • 4
  • 59
  • 113
  • 1
    Actually, (if it is true) proving $P=NP$ is NP-complete! And proving the opposite is probably NP-complete too! :) – rewritten Dec 02 '13 at 15:25
  • @rewritten what does that have to do with Kevin's answer? – Realz Slaw Dec 02 '13 at 18:56
  • +1, but actually, if there's a single problem in $NP$ that's not in $P$, then all $NP$-complete problems are not in $P$ – a06e Dec 02 '13 at 20:17
  • @RealzSlaw it is a further reflection on the intrinsic difficulty to prove the conjecture. It spawned from the first half of Kevin's answer, thus I felt like writing it here. – rewritten Dec 02 '13 at 20:25
  • @rewritten ah ok. I assume you mean that it is "NP-complete", in that a proof of it would be easy to recognize, thus a NTM could find it in polynomial time of the length of the proof. – Realz Slaw Dec 02 '13 at 20:40
  • It was just an intuition. After taking a quick look to the paper @nzv linked to, now I see that it's probably a known result. In the end, you explain it perfectly well, if a proof of it existed, then each single possible solution can be verified in P time, so the problem is actually NP. Or something like this. – rewritten Dec 02 '13 at 20:55
0

You've already accepted that showing a single NP-Complete problem to be in P, implies that they are all in P.

That means that if you prove that some NP-Complete problem (Let's call it A) is not in P, then none of them can be. Why? Because if one of the other problems were in P, then A would also. Which we know it's not.

Also, since P vs. NP is still an open problem, it means that we have NOT found any problems to be in NP that we know are not in P.

Cruncher
  • 778