Would proving P≠NP be harder than proving P=NP?

Problem Detail: 

Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP.

Let Q be one of known NP-hard problems. To prove P=NP, we need to design a single polynomial time algorithm A for Q and prove that A correctly solves Q.

To prove P$\neq$NP, we need to show that no polynomial time algorithm solves Q. In other words, we have to rule out all polynomial time algorithms.

I have heard people say this makes the second more difficult task (assuming that it is really true).

Is there a reason to think that proving P=NP (assuming that P=NP) would be easier than proving P$\neq$NP (assuming that P$\neq$NP)?

Asked By : Kaalouss

Answered By : Yuval Filmus

As Raphael explains, this question is ill-posed, since at most one of P=NP and P≠NP should be provable at all. However, a similar question arises in theoretical computer science in several guises, the most conspicuous of which is in the field of approximation algorithms.

Given an NP-hard optimization problem (say, maximization), we can ask how well we can approximate it. Proving an upper bound on the possible approximation is akin to P=NP, while proving a lower bound on the possible approximation is akin to P≠NP. The former is much easier than the latter. Indeed, to prove an upper bound all one has to do is to come up with an approximation algorithm and analyze it. In contrast, all known lower bounds are conditional: they are valid only if P≠NP (indeed, if P=NP then every NP-hard optimization problem would become solvable). To prove these lower bounds, we show that if we could approximate the problem too well, then we would obtain a polynomial time algorithm for some NP-hard problem. Usually this is done via the intricate technical machinery of the PCP theorem. This field, known as hardness of approximation, can be approached only be specialists, and is technical more challenging than most approximation algorithms. So in this case at least, P=NP is indeed easier than P≠NP.

Best Answer from StackOverflow

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