There is reason we still discuss Hilbert’s program, right? Hilbert was wrong about the answer, but his question was the right question and led to discovery of lots of new areas in math, including TCS (I can’t think of TCS without Turing machines and Turing machines without Hilbert’s program).

So the question is is P vs NP the right question? and the answer is absolutely!, just take a look at discoveries it has led to. I don’t agree with Scott’s answer, the world will be very different if P=NP, but that does not mean that the amazing structures and concepts that we have discovered during last 50 years will go away.

P vs NP is the Holy Grail, but it is not the only question.

]]>Actually it is with regards to the factorial function.

What about polynomially growing bits size $n^k$ bits? Say one has a solution to computing n! (factorial) in $log^{c}(n)$ steps but with arithmetic operations on size $n^k$ bits.

Would that be of any importance? Are such relations known? Are there any references?

]]>Needless to say, most people interpret this not as a practical proposal for solving PSPACE, but as an illustration of the hazards of the unit-cost model.

]]>Lipton’s weblog is discussing a recent preprint by Venkatesan Guruswami and Adam Smith, titled *Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate*. Guruswami and Smith are making progress with the (very tough) problem of error correction against, not random errors, but adversarial errors.

Focusing on the broad strategy of the Guruswami and Smith preprint, and ignoring the (very many) interesting details, their strategy is to change the starting premises of the problem, by restricting the adversarial errors to those errors that can be generated by a bounded-resource adversary.

This strategy allows Guruswami and Smith to prove what Dick Lipton calls a “pretty theorem” whose key ideas are “extremely appealing.”

Tim Gowers’ question seemed (to me) to be motivated by the idea of adopting a similar strategy for making progress in *P*-versus-*NP*, namely, change the starting premises of the problem by restricting the classes *P* and *NP* to problem instances that can be generated by adversaries having bounded computational resources.

Here the point is that a great many problems that are infeasible to solve when they are posed by an adversary having access to an omniscient oracle look *much* easier when they are posed by dumber adversaries. Guruswami and Smith’s preprint shows how this strategy can prove theorems that are concrete, powerful, and even “pretty.”

]]>Yet century-by-century in mathematics—and physics too—widely-accepted elements of naturality are set aside. For example, in the 19th century the naturality of Euclidean geometry was set aside, and in the 20th century, the naturality of Newtonian mechanics was set aside.

So we can ask, in the 21st century, what 20th century elements of physical and mathematical naturality are likely to undergo substantial evolution?

*Shtetl Optimized* grapples with two elements that are top candidates for 21st century evolution: (1) Hilbert state-spaces, and (2) the complexity classes *P* and *NP*.

The point is that there’s nothing wrong with the many theorems that have been proved about Hilbert space dynamics, and about the complexity classes *P* and *NP* … just as there is nothing wrong with theorems about Euclidean geometry and Newtonian dynamics.

Yet neither is it self-evident that these are the sole, or even the most natural, elements for building a 21st century understanding of physical dynamics and complexity.

Perhaps the safest expectation is that, in coming decades, students will learn the traditional 20th century elements of Hilbert space dynamics and *P*-vs-*NP* complexity classes, in conjunction with new dynamical state-spaces and new hierarchies of complexity classes, whose nature we are at present still struggling to grasp.

In short, among most important discoveries in each century are new, good, natural questions to ask … because very often, once we discover good questions to ask, good answers are not too hard to discover.

An outstanding weblog that regularly grapples with this class of questions is Dick Lipton’s *Gödel’s Lost Letter and P=NP*.