Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
“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 2 '13 at 14:32
    
@MJD I don't understand you can you please explain yourself in more details. –  Ilya_Gazman Dec 2 '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 2 '13 at 15:19
1  
I see now that the scope of "for any input" is unclear. I took it to mean "for any single input". –  MJD Dec 2 '13 at 15:34
    
its called lower bounds not "bottom bounds" –  vzn Dec 2 '13 at 17:36

5 Answers 5

up vote 5 down vote accepted

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)$.
share|improve this answer
    
I'm not sure that P=NP is actually provable right now. If you say so, it's probably not that easy though. –  user43400 Dec 2 '13 at 19:39
1  
@user43400 where do I say so? –  Realz Slaw Dec 2 '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. –  user43400 Dec 2 '13 at 19:44
1  
@user43400 what did I say that gave you that idea? –  Realz Slaw Dec 2 '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 2 '13 at 22:33

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.

share|improve this answer
    
"... then you will have effectively proved that there exists at least one $P$ such that $P=NP$..." –  Josué Dec 2 '13 at 19:47
1  
@JosuéMolina ?? P is P, see Realz Slaw's answer for a better explanation. –  rewritten Dec 2 '13 at 20:21

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!
share|improve this answer
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 2 '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 2 '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 2 '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 2 '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 2 '13 at 22:58

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.

share|improve this answer
1  
Actually, (if it is true) proving $P=NP$ is NP-complete! And proving the opposite is probably NP-complete too! :) –  rewritten Dec 2 '13 at 15:25
    
@rewritten what does that have to do with Kevin's answer? –  Realz Slaw Dec 2 '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$ –  becko Dec 2 '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 2 '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 2 '13 at 20:40

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.