Wednesday, February 08, 2006

Lovely quote by Stephen Jay Gould

From today's Quotes of the Day:
In science, 'fact' can only mean 'confirmed to such a degree that it would be perverse to withhold provisional assent.' I suppose that apples might start to rise tomorrow, but the possibility does not merit equal time in physics classrooms.
No, I am not about to enter into an Inane Debate about intelligent design. That is too far on the road away from science, past the exit for philosophy, just before the religion rest stop.

I am wondering about provisional computer science theories like P ≠ NP. It seems to me that we're closer to ID people on this than to scientists or even philosophers. Do we even have a philosophical or socio-philosophical reason why this must be true or linked with other deeper philosophical questions? (e.g., If P = NP, then (using reasonable laws of physics) the universe should have evolved a lot faster than it did, or that the future would be a lot closer than it is, etc., or If P = NP, there cannot be free will, or If P = NP, then there would be no poverty in the world, etc.)


Suresh said...

Is that really fair ? On the one hand, we are close to ID in the sense that "we can't imagine P = NP because lots of smart people have tried and failed".

On the other hand, we believe "P != NP" because all reasonable models of computation invented thus far (quantum is a problematic case) do not appear to transcend the polynomial-nondeterministic polynomial boundary (i.e the effective CT thesis). This latter interpretation seems much more like the inductive arguments in favor of scientific laws than the "we can't imagine it, so it can't be true" argument of IDiots.

Anonymous said...

P != NP is a "mathematical"
question, not a natural science
question. In that regard it is
the same as the Riemann hypothesis,
people believe it for all kinds
of reasons some technical and some
psychological. I don't understand
where Siva is going with his
comparision to TCS people acting
like ID people. In papers we almost
always say "if P!=NP" or "unless P=NP" etc. This is in contrast to
some physicists who go about
claiming that quantum computers
can solve NP-Complete problems
in polynomial time without any
formal evidence.

Anonymous said...

Actually, we are probably the best qualified to challenge Intelligent Design: don't we know both on the one hand how randomness can produce very non-random looking patterns, and on the other, how to "design" things that look indistinguishable from random chance?

Anonymous said...

If you are referring to what gets said in a course on complexity theory, then I agree with the second poster who notes that we always "hedge our bets" by saying "we believe that..." without saying dogmatically that it is true.

If you are referring to what gets said in other CS courses, then I think the point is that *according to current knowledge* P \neq NP since we don't have poly-time algorithms for NP-complete problems. (And so if one is trying to solve an NP-complete problem *now*, then you may as well take P \neq NP.)

Andrei Lopatenko said...

Perhaps, the existence of undecidable problems os much more important from philosohical problem of view, then unsolvability of some problems by determenistic Turing machines in PTIME