polynomial vs exponential time problems clarification

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