Thursday, August 6, 2009

Problems, solutions and verification

Puzzles are fun. But what is a puzzle really. Puzzles are a class of problems that have been solved before. In this essay, I want to draw your attention to three classes of problems: puzzles, near-puzzles and theories.

The first class comprises the sort of problems for which a known algorithm exists to get us to the solution. These types of problems have the property that as soon as we identify their type (i.e. that it is a puzzle like one I have already solved), we just need to apply the correct formula and eventually we will get the answer. Let's call the class of these puzzle type problems, P.

The second class of problems are problems, for which, while no algorithm may exist to reach a solution, if a solution is offered, it could be tested and shown to be a solution. Since these problems are similar to puzzles, we'll call the class of near-puzzle type problems, NP.

There is a third class of problems. These are the problems that have not been solved, and/or if a solution existed, the solution could not be verified. This class of problems are similar to theories, and therefore we'll call the class of theory-type problems, T.

Some examples

Summation. Summation is a kind of "puzzle." The summation puzzle asks, "For any two numbers, what number is their resulting sum?" We know that this puzzle is a P-type problem since there is a strict rule for summation of any two numbers and the rule always generates the answer.

Temporal questions. One cannot predict the future. I can be pretty sure, but I can't be certain about it until it has safely become the past. So problems like what will I have for lunch tomorrow is a NP-type problem. I may think it will be a peanut butter and jelly sandwich, but until I have it, I can't be sure. Of course, these solutions can be verified simply by waiting long enough.

Theory verification. Some problems are problems that relate to the truth of general theories. Theory verification has been known to be a general problem for a long time in the philosophy of science. Given any scientific theory there is no way to prove that it is true. For example, if I have a theory that has some explanatory power, such as, "Evolution via natural selection is an explanatory principle for the myriad complex living organisms that exist today," it pertains as an explanation until it doesn't. That is, until I find enough scientific data that debunk it (such as serious inconsistencies in the fossil record, for example) I can believe it to be true. This is true of all scientific theories, even the historically unexceptionable ones like quantum mechanics or the modern evolutionary synthesis.

Is the Goldbach Conjecture P, NP or T?

GC: "Every even integer greater than 2 can be written as the sum of two primes"

Let's presume, as Euler may have, that the GC is true but not provable. This conjecture would belong to the T-type problems.

However, if it were false, then it would presumably belong to the NP class (would be verifiable), and by extension, belong to the P class since the counter-example would be a finite number and an algorithm that checked every even integer greater than 2 would be a valid algorithm.

Some interesting properties of P's and NP's.

You may have noticed that the class of P problems are very similar to NP problems, in some regards. Unlike T problems, an NP problem is similar to a P problem, in that, given its solution, it can be verified. We could certainly imagine mistaking a P-type problem for an NP-type problem in cases where we didn't notice that it was the same riddle in a different frame, figuratively speaking. Another interesting feature of P-type problems is that it is not inconsistent to classify them as NP problems. All P-type problems are NP-type problems. Notice, if the reverse is true, then near-puzzles would be puzzles.

Given all the similarities, we may begin to suspect that, in actual fact, P=NP. It is at least possible that for all those NP-type questions, they are really P-type questions, and it is our own limited knowledge that has allowed us to initially misclassify them. How could we find out? Does P=NP? That is an interesting problem. Is that problem, itself, a P-, NP- or T-type problem?

Classifying "P=NP?"

Assuming that "P=NP?" is one of the three, it is either the case that "P=NP?" is a P- (and therefore also NP), NP- or T-type problem.

Let's write out the question completely. The question we are asking is, "Is the problem 'Are all puzzle type problems the same as all near-puzzle type problems?' a member of P or NP or T?"

It is possible that the question does not belong to P or NP (case: not P, not NP).

In this case, the question could belong to the T-type questions. If that were the case, then there would be no way to satisfactorily answer "P=NP?". It is possible that it could be true that P=NP, but there would be no way to prove it. This is similar to the incompleteness result guaranteed in sufficiently complex (and consistent) formal systems as explained by Gödel.

Let's presuppose that there is a solution to this problem and set aside the possibility that the general question is a T-type problem. The following two possibilities would remain ([not P but NP] or [P and NP])

It is possible that the question does not belong to P but does belong to NP (case: not P but NP).

In this case, it is clear that the underlying question "P=NP?" would need to be false since if it were the case that P=NP, the above presupposition (not P but NP) would be meaningless. Assuming that the above presupposition is not meaningless, it must be the case that P≠NP. However, it is not consistent for the question "P=NP?" to be a member of NP (and not P) and to show that P≠NP. For, if we were able to definitively show that P≠NP, then the question "P=NP?" must be a member of P and NP (the solution algorithm thereby classifying it as P would of course be this proof!).

Continuing to assume that the question is not a T-type question, it follows that the only choice that remains is that the question belongs to P and (trivially) NP (case: P and NP).

If the problem "P=NP?" is a member of P, this means that the question "Are all puzzles and near-puzzles equivalent?" has a solution and there is an algorithm to demonstrate it! Either P=NP or P≠NP.

If P=NP, we must be capable of imagining an algorithm existing, which can rule out any problems with algorithmically verifiable solutions, for which, no algorithm can provide the solution (an algorithm exists and it rules out NP-type problems that are not also P-type). This should be an easy task since we have already assumed that there exists an algorithm that has solved the harder problem "P=NP?" It is a contradiction in terms to suppose that an algorithm that can verify solutions cannot also generate solutions themselves. For example, the algorithm, try all potential solutions one at a time would be a viable algorithm for any problem one can suppose.

Notice that since we have assumed that there is a solution to the problem (that it is not a T-type problem) we have implicitly eliminated all true but unprovable claims from the pot of questions that are valid. Under these premises we are assuming that an algorithm doesn't get stuck checking the types of problems that would ultimately be T-type problems. If we know a priori which types of problems these are, then we guarantee that all our searches for solutions will terminate, and in that case, the search space is finite. This guarantees that P=NP.

For similar reasons as above, we have ruled out the possibility that P≠NP. For that to be true, it must be possible for there to exist an algorithm that can identify at least one problem for which solutions, if found, could be verified and further, the algorithm must show that for this problem there exists no algorithm one might use to find a solution. Further, this algorithm must be able to reconcile this fact with the fact that the more general problem is P=NP? is itself a P-type problem. Just as before, there is no way that P≠NP is a solution given the particular search space to which we have confined ourselves.

Conclusions

I have shown that either "P=NP?" has no solution (i.e. it is a theory type question) or P=NP. I have purposefully used the computer science terminology in their own P vs. NP debate because I believe the argument above is at least useful as an analogy. Unlike the computer science debate, the above has not made specific mention of an algorithm's time scaling with respect to a given input, which is of course a very important detail. For example, algorithms with exponential time solutions would still be members of P according to the above argument, while they would be excluded from P in the computer science version of the argument.

No comments:

Post a Comment