- 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 20:29:43 -0700

hi all. re: the exponential vs polynomial time thread.

imho HFs comments could be interpreted as roughly correct

but stated in a very confusing way & I would say, hence

the ensuing confusion. lets give this another shot.

there are no problems for which it has been proven that

there is a **lower bound** of exponential time except

for those that also require exponential space (for which

the exponential time lower bound is trivial). (space is

the number of tape squares used by a TM, time is the number

of steps). this of course is quite frustrating & even embarrassing

to researchers and a gaping open problem in the theory.

the big P!=NP problem depends on showing that there is some

P-space problem that has a lower bound of exponential time, i.e.

it cannot be solved "any faster" than exponential time.

literally, there are many problems for which it has been shown or even

"proven" that they can be verified in P time and can

be solved in exponential time.

in fact every NP complete problem has this property. what has

not been proven or is not known is that exponential time is

also a **lower bound**.

so it can be very confusing if someone says: there are no

problems that are known to be checkable/verifiable in P time but take

exponential time. the term "take" must be used very carefully, imho

it should be avoided as just too ambiguous.

sometimes people mean as a lower bound (as HF did below), or

sometimes it just means "a solution exists at that speed" (as I write

above).

forget NP complete for a minute &

suppose I have a problem that is solvable in P time. does it

"take" exponential time? in one sense, yes, there exists also

algorithms that run in exponential time to solve it. but in another

sense, no, that is not the lower bound, the lower bound is polynomial.

also note that defining NP in terms of "verification in P time"

is done in terms of a regular deterministic TM machine, not

an nondeterministic one. the sense that NP

can be defined in terms of nondeterministic

TMs is: it is the set of problems that can be solved by nondeterministic

TMs in P time.

that straightens it all out, right???

there are many different ways to look at the P vs NP problem,

in this way it is like g"odel's problem, and this can lead

to knowledge in the sense that "a little knowledge is a

dangerous thing"..

HF writes

*>> On 31-Dec-02, Hal Finney wrote:
*

*>> > One correction, there are no known problems which take exponential
*

*>> > time but which can be checked in polynomial time. If such a problem
*

*>> > could be found it would prove that P != NP, one of the greatest
*

*>> > unsolved problems in computability theory.
*

*>>
*

*>> What about Hamiltonian circuits or factoring an integer or roots of a
*

*>> Diophantine equation?
*

*>
*

*>I don't believe any of those are known to take exponential time. For all
*

*>we know a polynomial time solution may yet be found for all of these.
*

HM writes

*>Communications glitch here. The definition
*

*>of NP is problems that can be solved in
*

*>polynomial time on a "nondeterministic"
*

*>machine, that is one that can test
*

*>simultaneously all candidate solutions
*

*>(effectively by creating exponentially
*

*>many processes for testing all possible
*

*>combinations of undetermined variables,
*

*>each individual combination taking polynomial
*

*>time to check)
*

Received on Mon Dec 30 2002 - 22:44:36 PST

Date: Mon, 30 Dec 2002 20:29:43 -0700

hi all. re: the exponential vs polynomial time thread.

imho HFs comments could be interpreted as roughly correct

but stated in a very confusing way & I would say, hence

the ensuing confusion. lets give this another shot.

there are no problems for which it has been proven that

there is a **lower bound** of exponential time except

for those that also require exponential space (for which

the exponential time lower bound is trivial). (space is

the number of tape squares used by a TM, time is the number

of steps). this of course is quite frustrating & even embarrassing

to researchers and a gaping open problem in the theory.

the big P!=NP problem depends on showing that there is some

P-space problem that has a lower bound of exponential time, i.e.

it cannot be solved "any faster" than exponential time.

literally, there are many problems for which it has been shown or even

"proven" that they can be verified in P time and can

be solved in exponential time.

in fact every NP complete problem has this property. what has

not been proven or is not known is that exponential time is

also a **lower bound**.

so it can be very confusing if someone says: there are no

problems that are known to be checkable/verifiable in P time but take

exponential time. the term "take" must be used very carefully, imho

it should be avoided as just too ambiguous.

sometimes people mean as a lower bound (as HF did below), or

sometimes it just means "a solution exists at that speed" (as I write

above).

forget NP complete for a minute &

suppose I have a problem that is solvable in P time. does it

"take" exponential time? in one sense, yes, there exists also

algorithms that run in exponential time to solve it. but in another

sense, no, that is not the lower bound, the lower bound is polynomial.

also note that defining NP in terms of "verification in P time"

is done in terms of a regular deterministic TM machine, not

an nondeterministic one. the sense that NP

can be defined in terms of nondeterministic

TMs is: it is the set of problems that can be solved by nondeterministic

TMs in P time.

that straightens it all out, right???

there are many different ways to look at the P vs NP problem,

in this way it is like g"odel's problem, and this can lead

to knowledge in the sense that "a little knowledge is a

dangerous thing"..

HF writes

HM writes

Received on Mon Dec 30 2002 - 22:44:36 PST

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