| > - “p” - a category of problems which can be solved in O(n²) > - “np” - a category of problems which can be checked, but not solved, in O(n²) These definitions are incorrect. Certainly there are other polynomials than just n².
P is the complexity class wherein the problem can be solved on a Turing machine in a number of steps equal to some polynomial of the size of the input. For NP, replace "Turing machine" with "nondeterministic Turing machine" and otherwise it's the same.
The 'size of the input' is the count of symbols on the machine's tape, allowing for the input to be written in any finite alphabet, chosen by the designer of the Turing machine. Nondeterministic can mean different things in different contexts, so I want to clarify. Here, nondeterministic means that the machine does the 'impossible' thing of forking itself and running up to an infinite number of copies of the deterministic machines (including distinct copies of their state) at the same time, then if one of the computations succeeds then that computation is kept and the others are discarded (including the count of how many steps they spent). This is why, if you have a machine that can check a problem in P, you can make the machine to solve it in NP by wrapping your checker in "use nondeterminism to generate every possible input value" and simultaneously check them all. I highly recommend the theory of computation course at MIT, which is freely available online: https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/
https://www.youtube.com/playlist?list=PLidiQIHRzpXIFFbyGrWkqXXVj0BztDcTF
I found the course very approachable.> All information necessary to generate checkable solutions to any problem must be encoded in the problem itself, or the problem would be undecidable, because there would be no way to check a solution against a problem if the problem and solution were completely unrelated. This is actually a great insight, but you must keep in mind that if I tell you that the solution to "a > b" is True, you cannot find a and b. You are touching on an important concept in computer science theory called "reversible computing". It's also related to information theory. If I have a machine that solves the travelling salesman problem that outputs "the fastest route is from B to C to A", then you must ask yourself whether there are multiple different inputs to the problem which can generate that output? (You don't always have the freedom to change the input type of the problem, or else I could factor integers in constant time by demanding that all integers must be input as a product of primes.) When the values are computable from the other, the question remains about the number of steps it takes to do. You still have to show that it's bounded above by some polynomial, and then that this is true for all problems in NP. We already have ways to rewrite one NP problem into another, and so showing a single machine that takes polynomial steps to solve any of those NP problems would suffice to show that P = NP. This is how we've proven lots of complexity classes the same in the past. On the other hand, we have almost no techniques which prove that two complexity classes are distinct. |