NP-Complete – How to Prove that P ? NP

np-complete

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.

Best Answer

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)$.
Related Question