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/