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)