P!=NP in the news

[davar55]

Originally Posted by CRGreathouse

Not that I agree with the sentiment, but I think the theory is that if P = NP, proving theorem is easy, so who needs a mathematician? Just hook up the polynomial-time SAT solver computer.

Mathematicians count.

[xilman]

Originally Posted by davar55

Mathematicians count.

Perhaps. I always thought that mathematicians worked it out with a pencil and paper.

Astronomers, on the other hand, tend to do it at night whereas cosmologists do it with a Big Bang and politicians do it to everyone.


Paul

[davieddy]

Originally Posted by xilman

Perhaps. I always thought that mathematicians worked it out with a pencil and paper.

Paul

And logs..... but only when constipated.

David

[R.D. Silverman]

Originally Posted by xilman

Perhaps. I always thought that mathematicians worked it out with a pencil and paper.

Astronomers, on the other hand, tend to do it at night whereas cosmologists do it with a Big Bang and politicians do it to everyone.


Paul

Nah. Mathematicians do it both continuously and discretely.

[only_human]

This is a follow-up posted on an IBM research site: http://www.almaden.ibm.com/cs/disciplines/pm/#PvNPtalk

What's all this about P not equaling NP?

Recently there was considerable interest in a proposed proof that P is not equal to NP. In response to that interest, some members of the theory group gave a talk to describe, for a general scientific audience, some aspects of this work and the community's analysis of it.
(The video starts a little bit into the talk; the speakers are Ken Clarkson, Ron Fagin, and Ryan Williams, in that order; the "D." referred to is Vinay Deolalikar, the author of the proposed proof.)
Video of the talk (including all but the first few slides)
The slides

I've made text format changes to the following slides here but intend no factual changes:

Strategy of Deolalikar’s Proof

If k-SAT were in P, then the solution spaces for all k-SAT formulas would have a “simple structure”.
For some k-SAT formulas, the solution spaces for these formulas do not have a simple structure.
Therefore, k-SAT is not in P, and so P ≠ NP.

Deolalikar proposes to choose certain random
k-SAT formulas, and use known properties of their solution spaces

The last two slides paraphrase the problems by analogy and offer concluding remarks:

Can we salvage something from it?

• Terence Tao's car analogy (paraphrased):

…the paper is like a lengthy blueprint for a revolutionary new car, that somehow combines a high-tech engine with advanced fuel injection to get 200 miles to the gallon.

The LFP objections are like a discovery of serious wiring faults in the engine… but the inventor claims this can be fixed using a weak engine

The solution space objections are like a discovery that, according to blueprints, the car would run just as well if gasoline was replaced with ordinary tap water… D.’s response to this has been roughly “That objection is invalid – everyone knows cars can’t run on water.”

The theorem (on the previous slide )

[edit: this is the gist]
[Theorem (Proved by "vloodin" and Terence Tao)
Under the notion of “simple" given in the paper, k-SAT does have simple solution spaces!]

is like a discovery that the fuel is in fact being sent to a completely different component of the car than the engine…"

• Can any parts of this car be salvaged?

Concluding remarks

• Deolalikar’s proof seems to be not only wrong, but unfixable.
• Hardness and solution space complexity seem to be orthogonal.

- New research question: can random k-SAT be used to prove complexity results?

• There is a new world of community refereeing.

- Good: every part of the proof had corresponding experts
- Bad: those experts spent a great deal of time
- The community is still learning how to work effectively in this new world,