P (does not equal) NP (in process)
My understanding of the P=NP question is basically: can a solution be found for any problem where the solution can be confirmed/checked? This argument is based on that understanding of the question, I'll go back and check the core assumption later.
So let's assume P=NP in almost all cases (with a limit as the number of problems approaches infinite, within the realm of all possibile problems). This problem can always be posed: can a problem be found using this problem solving method such that the solution cannot be found using this problem solving method. Said another way, "can this algorithm be used to identify a problem that it cannot then be used to solve."
The issue is that is the answer is yes, then P does not equal NP, because that result would negate the claim. If the answer is no, then P does not equal NP because the issue of finding said problem cannot be resolved, the lack of additional problems becomes the unresolvable problem.
The reason I highlight realms here is because the very nature of asking this question, and pushing it to the true limit would involve discovering a functionally infinite field of problems that can be solved with this method. The specific problem that remains unsolveable, once identified, would represent a boundary to another realm.
For example, if a problem were specifically found that P could provably not be used to resolve, given perfect information, then another type of method would almost certainly be revealed that could resolve it, even if the nature of said method were not deeply understood. By applying the assumptions of said method to known problems, more would be discerned about it, and the product of having already used P, and now using this new method (Q) would create a new realm of understanding until Q could be understood and potentially used as a problem solving tool in its own right. There would be a whole realm of problems that Q could then be used to solve that could not be solved or even seen through the methods of P. This process of uncovering completely new problem solving techniques (not new algorithms in this case but something that functioned on the order of an algorithm to solve problems but was completely different), would likely continue for a considerable time.
Comments
Post a Comment