[Solved]: How to prove P$\neq$NP?

Problem Detail: 

I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point.

We can show that P $=$ NP if and only if we can design an algorithm that solves any given instance of problem in NP in polynomial time.

However, I do not understand how on earth can we prove that P$\neq$NP. Please excuse me for the following similitude as it might be so irrelevant, but telling someone to prove if P is not equal to NP appears to me like telling someone to prove that God does not exists.

There is a set of problems, those are unable to be solved by a Non-deterministic Finite Automata (NFA) with polynomial number of states regardless of the current technology (I know this is a sloppy definition). In addition, we have a considerably large set of algorithms that makes some crucial problems (shortest path, minimum spanning tree, and even sum of integers $1 + 2 + \dots + n$) polynomial-time problems.

My question in short: If I believe that P $=$ NP, you would say "then show your algorithm that solves an NP problem in polynomial time!". Suppose that I believe P$\neq$NP. Then what would you exactly ask? What would you want me to show?

The answer is clearly "your proof". However, what kind of proof shows that an algorithm cannot exist? (in this case, a polynomial time algorithm for an NP problem)

Asked By : cagirici

Answered By : David Richerby

There are three main ways I'm aware of that could prove that P$\,\neq\,$NP.

1. Showing that there is some problem that is in NP but not in P. You're probably familiar with the proof that comparison-based sorting need time $\Omega(n\log n)$ to sort a list of $n$ items. One could, in principle, produce a similar proof showing that 3SAT or some other NP-complete problem can't be solved in time $O(n^c)$ for any constant $c$. Geometric Complexity Theory seeks to use tools from algebraic geometry and group representation theory to prove such lower bounds, by considering the symmetries that problems possess. Circuit Complexity is another.

2. Showing that P and NP have different structural properties. For example, P is closed under complementation. If you could show that NP$\,\neq\,$co-NP (i.e., that NP is not closed under complementation), then is must be that P$\,\neq\,$NP. Of course, this is just pushing the problem one level deeper – how would you prove that NP$\,\neq\,$co-NP?

   Another possibility is that we know that NP is exactly the class of problems that can be defined in something called existential second-order logic. If one could show that there's no logic corresponding exactly to P (or if there is a logic but it's different to $\exists\mathrm{SO}$), then P and NP must be different. A related (in fact, equivalent) idea is to show that P doesn't have complete problems under reductions defined by first-order logic, since it's known that NP does have complete problems under these reductions.

3. Prove that some problem isn't NP-complete. If P$\,=\,$NP, then every non-trivial problem in NP is NP-complete under polynomial-time many-one reductions ("non-trivial" here means not $\emptyset$ or $\Sigma^*$). So, if you can show that some problem in NP isn't NP-complete, then we must have P$\,\neq\,$NP.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50362