Question

I have a question about the p-np problem. If a p-np problem is assumed to be np-hard, why do both true and false problems arise?

Answer 1

As best I can tell, I think your issue is that you don’t know the proper definition for “problem” which P=NP is talking about.

The short version is that “the p-np problem” is NOT the type of problem which this field of math (Complexity Theory) talks about. The P=NP problem is asking “is every NP set also a P set?” I don’t think this can be phrased as a problem of the same type (a set of numbers).

One of the ways to prove P=NP is to show that some NP-hard problem (a problem at least as hard as any NP problem) is a P problem. You seem to understand this. But P=NP is not an NP problem- it isn’t even really the type of problem which can be classified as P or NP or anything like that.

Let me know if this did or didn’t make any sense.

If it helps, here’s a vastly oversimplified version of what P=NP means: “if there’s a hint I can give you that makes a problem easy, does that mean the problem, even without the hint, was easy already?”

Answer 2

Complexity classes like P and NP are used to classify problems that take in some sort of input and return a yes-or-no answer based on that input. For example, the traveling salesman problem takes in a list of cities (with associated distances between them), and the answer will depend on those cities. The P-NP problem is not of that type, since there's no input parameter that the answer depends on: it's just a single yes-or-no question. So the P-NP problem isn't the sort of thing that we would usually classify as P, NP, or any such complexity class.