hi all. Ive been poking at computational complexity theory to various
degrees for close to a decade.
the recent comments on the subject are interesting & its not
surprising it has popped up on this list.
I believe complexity theory is going to shed some deep
new light on physics, and has already done so. one area of
intense study is the satisfiability "transition point" which
has many deep analogies to physics and thermodynamics under
very active investigation. I can cite some refs if
there is interest.
one of the deepest analogies yet to be explored, I suspect,
is that of entropy. in physics,
entropy is a measure of disorder. I suspect in
complexity theory, hardness of a problem is a measure/analog of
entropy. the more disorder involved in the computational function,
the more difficult.
another thing to point out here. while there are no proofs that
P!=NP, there are some good results in computational complexity
theory separating some complexity classes. its a very active
area of research.
one of my most favorite results Ive been getting
into lately is that it has been proven that some problems require
an exponential # of AND,OR circuit "families" (by razborov in 1985,
for which he won the nevinlanna prize). if it could be
proven for an NP complete problem and AND,OR,NOT gates, then P!=NP.
hans moravec (wow, welcome to the list!!) writes:
>By the way, it is known that factoring into
>primes is easier than the TSP.
as HF pointed out, factoring has not been proven to be NP
complete or easier than NP complete
(it is conjectured to be easier than NP hard) in any sense
as far as I know. this is definitely a very cutting edge
area of research. shor's quantum-P-time factoring algorithm is definitely
one of the very important breakthroughs in this area.
let us note some of the other key open questions. it is
not known if quantum computers can solve NP complete problems
in P time in general. it is not known how to "most efficiently
convert" an arbitrary algorithm to a quantum algorithm, although
there are hints of this (disordered database lookup, shor's
factoring algorithm, etc)
re: qm computing, I highly recommend julian browns outstanding book
"quest for the quantum computer" which I recently finished,
much good food for thought for anyone on this list.
many of these themes can be found in the revised theory-edge
FAQ v2.0 (qm computers,satisfiability problem,complexity theory,etc)
http://groups.yahoo.com/group/theory-edge/message/6585/
Received on Mon Dec 30 2002 - 22:01:22 PST