[P Versus NP]

Truth and Perfection

Posts Tagged ‘Resolved

Gödel admits P=NP

leave a comment »

On P=NP: Godel, who was born to illiterate farm workers in Minot, North Dakota ... finally said Fine! OK! We believe your freaken theorem, OK? Jesus.

Gödel, who was born to illiterate farm workers in Minot, North Dakota finally said, "Fine! OK! We believe your freaken theorem, OK? Jesus."

Why Undecidability is Too Important to be Left to Gödel  ∞

JOHN L. CASTIGodel, who was born to illiterate farm workers in Minot, North Dakota ... finally said Fine! OK! We believe your freaken theorem, OK?

How difficult is it to answer a question like “Where will the Dow Jones industrial Average sit at the end of 1994?”, or “What are the odds of the Dallas Cowboys repeating as the NFL champions?”, or even “On what day will the Santa Fe Institute really move to its new campus off Hyde Park Road?”

While none of these questions is particularly “scientific,” at least in the usual sense of that term, they all have far more immediacy and importance for the daily lives of most of us than do far more scientifically respectable queries such as “What is minimal cost of touring the 50 state capitals?” or “What is the “complexity” of Champernowne’s number?” The point here is that the traditional measures of computational and algorithmic complexity as used in mathematics and computer science don’t even begin to characterize the difficulties inherent in trying to come up with believable, let alone correct, answers to these sorts of questions. So there most certainly are limits to our knowledge – scientific or otherwise.

But for the most part these limits are not the kind envisioned by Gödel, Turing, and their many able successors. Rather they are limits of a far subtler and more insidious kind: limits due to the ill-posed nature of most questions, limits stemming from the vagueness in natural human languages, limits coming from our inability to make error-free measurements, limits arising out of weaknesses in our standard modes of reasoning and, in general, limits generated by the inherently complicated mutual interactions between the many components of most natural and human systems.

So, in my view the most productive way to go about understanding whether or not any of these kinds of limits to our knowledge are permanent or merely temporary barriers to our understanding of the world we live in is to think about the development of new ways of looking at complexity in formal terms, ways that more faithfully mirror our informal ideas about what is and isn’t “complex.” These ways must necessarily include the crucially important fact that real-world complexity (whatever that might be) is not a context-free property of anything. Like truth, beauty, justice and “the good,” complexity resides as much in the eye of the beholder as it in the beholden.

Whatever such a real-world measure of complexity turns out to involve, almost certainly will not be something as simple and naive as a single number characterizing the complexity of a given problem, question or situation. Rather, I envision it being some kind of multi-criterion, interactive type of measure, saying in effect that some kinds of problems are very complex indeed if you attack them by, say, deductive modes of reasoning, but evaporate away like trickle of water in the desert if you use other modes of reasoning like induction, abduction or (fill in your favorite “-ism” here). Sad to say, I have no such “grand unified theory of complexity” to offer up for your entertainment at the moment. But all my intuitions say that such a theory is not beyond hope.

Furthermore, I feel strongly that only when a skeletal framework of this kind of theory emerges will we finally be on the way to banishing the ghost of Gödel from the scientific banquet table.


Written by pversusnp

May 6, 2009 at 12:58 pm

Posted in Perfection

Tagged with ,