What is the evidence that P could equal NP?
I guess this is the same as asking:
If it's known that $P \subseteq NP$ (depending on standard), then why is this not enough? Why assume that P could equal NP?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
This is a rather strange question to ask, given that a large majority of complexity theorists believe that P is different from NP. All the evidence we have points at P being different from NP, which is why most people believe that P doesn't equal NP.
It's like asking a climate scientist for the evidence that there is no connection between global warming and greenhouse gasses. The main difference is the standard of proof involved. The climate scientist is content with trying to convince you that there is strong evidence for anthropogenic global warming. The complexity theorist's goal is a proof, and she would not settle for less.
That said, much of complexity theory tacitly relies upon P being different from NP: if P were to equal NP, many of the results would be meaningless. Officially, such results are stated as "if P$\neq$NP then X" (such results are known as conditional results). However, the perceived semantics is simply "X holds".
Sometimes the results need a strong assumption, "if A then X", for various different As. The weaker the A, the stronger the result. Some of the assumptions A don't enjoy widespread acceptance, for example the Unique Games Conjecture. Others are considered pretty likely, such as the (Strong) Exponential Time Hypothesis. All of these are stronger assumption than P$\neq$NP (that is, they imply that P$\neq$NP).
What evidence suggests that P could be equal to NP?
This is simple: it seems counterintuitive, especially to a layperson, that a problem might be significantly harder to solve than to check.
Currently, most theoreticians believe that P$\not=$NP; that is, whatever evidence that they could be equal is not currently very strong.
Is it important whether P=NP?
Yes. This is incredibly important for many reasons.
On the one hand, if P=NP, this means that many tasks that we currently consider computationally infeasible will be feasible; an algorithm that solves an NP-complete problem in polynomial time would revolutionize the world.
On the other hand, many cryptographic techniques rely on certain problems being "hard." That is, they rely on the fact that solving the problem will take more resources (time and computation) than a cracker would reasonably possess. Obviously, the problems on which security is based need to be in NP (we must be able to guarantee that the provided solution is correct), but they should not be in P, since that would mean the solution is easy to reverse engineer. As it stands, most theoreticians believe that P$\not=$NP. However, until it is established one way or the other, we cannot actually guarantee our cryptographic security systems.