• Josh

P≠NP In Your Mind

Updated: Feb 4

One of the biggest open problems in computer science is the question of whether "P=NP" is true. Simply put, it is something like asking: if the solution to a problem can be verified easily (making it "NP"), does this imply that it can be solved easily too (making it "P")? If P≠NP, that would imply that some problems are hard to solve but easy to verify.


It might seem intuitively that P≠NP because some problems are hard. However, (a) solutions to truly hard problems might also be hard to verify without violating P=NP, and (b) many problems previously thought to be hard have been found to be reducible to easier ones, that are both easy to solve and easy to verify. In any case, the general question remains unanswered, though a solution is worth $1M to the first person to crack it.


There's an analogue in your mind, which has to do with solving actual Real World problems. Whether you're trying to fix your car and don't know which tool to use, or you're stranded on a desert island and need to find food, you may be very well-equipped to check the efficacy of a solution you already have in hand, but the hardest part is often thinking of something to try in the first place. You might be standing there, tools ready, ready to do something, but still be totally stuck because you haven't thought of something to do yet.


Call it foresight; call it inventiveness; call it creativity; call it what you like, but there's no reason someone who excels at thinking up a solution will necessarily excel at implementing the solution (and vice-versa). On reflection, the two tasks share very little in common: one is figuring out and the other is acting out; one is potential and the other is kinetic; one is true theory and the other is experiment (or at least applied theory). Concepts fall into the same categories; you can't understand something until you think of it (P part), but once you've thought of it you can run it through all of your standard checks for consistency (NP part).


Pirsig points out that, for all the power of the Scientific Method in confirming or refuting hypotheses, there's no explanation within science for where those hypotheses come from in the first place. It's as though science is built totally on principles of verification and not on "real problem solving" in the sense above; the latter does in fact get done, but only through mechanisms that are totally lacking in explanation. Pirsig thinks it's because of an undefinable Quality-force that undergirds the entire universe. I think part of the answer is that your brain knows much more than you do. In any case, the process of solving (P-part) seems very much independent of and complementary to the process of verifying (NP-part).


So while this may not be worth $1M, I'm very confident that P≠NP in your mind.

7 views0 comments

Recent Posts

See All