- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: <vznuri.domain.name.hidden>

Date: Mon, 30 Dec 2002 19:46:30 -0700

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

Date: Mon, 30 Dec 2002 19:46:30 -0700

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:

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*