examples of EXPTIME
d. lee
Could anyone show me other examples in EXPTIME?
Online list of problems will be helpful.
Many thanks in advance.
Kent Paul Dolan
> I heared that deciding winner of go-game is in
> EXPTIME.
I'm guessing that's "the problem of determing
whether the first or the second player in Go can
force a win" and also that such a claim must be
speculation, or with respect to one particular
brute force algorithm.
> Could anyone show me other examples in EXPTIME?
The "Traveling Salesman Problem" is one of the
paradigmatic examples. It's brute force solution
time grows as N! where N is the number of cities to
be visited in shortest cyclic order. Its best known
direct solution technique is something called
"branch and cut", IIRC, a modification of "simplex
method" search/optimization technology, of which
former algorithm I can never find a description
complete enough to turn into software. It's
essential paper predates softcopy technical papers,
sadly, and also the holdings of the local university
library, and every paper since, incorporates so much
stuff by reference from that (perhaps 1957) paper as
to render the later papers unusable.
With branch and cut, a problem of around 15,000
nodes was once solved by heroic effort using
networked microcomputers.
Unfortunately, practical problems, such as
integrated circuit wire routing, have node counts in
the low several millions these days, far outside any
but heuristic "solution" approaches' competencies.
> Online list of problems will be helpful.
This page has a pretty picture to show you how deep
and complex are the waters into which you are
sticking a toe:
http://www.cs.umass.edu/~immerman/descriptive_complexity.html
Run away, run away! <grin>
This search's output contains much of interest on
the subject (and a lot of tares as well, of course):
http://www.google.com/search?q=exptime+computability+survey
HTH
xanthian.
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
Michael N. Christoff
"d. lee" <dongh...@hotmail.com> wrote in message
news:61d68280.04090...@posting.google.com...
I assume by EXPTIME you mean EXPTIME-complete. For example, all O(n)
algorithms are EXPTIME since P is in EXPTIME. I'm sure others can fill in
the blanks but: as far as complexity class separations between P, NP and
EXPTIME, we've only been able to show that P is a strict subset of EXPTIME.
So even if an algorithm is EXPTIME-complete, all we can say for sure is that
it requires more than polynomial time to solve, not that it needs at least
exponential time.
Examples of games that are EXPTIME-complete include chess and checkers .
l8r, Mike N. Christoff
Abdulaziz Ghuloum
> "d. lee" <dongh...@hotmail.com> wrote in message
> news:61d68280.04090...@posting.google.com...
>
>>I heared that deciding winner of go-game is in EXPTIME.
>>Could anyone show me other examples in EXPTIME?
>>Online list of problems will be helpful.
>>
>>Many thanks in advance.
>
>
> I assume by EXPTIME you mean EXPTIME-complete. For example, all O(n)
> algorithms are EXPTIME since P is in EXPTIME. I'm sure others can fill in
> the blanks but: as far as complexity class separations between P, NP and
> EXPTIME, we've only been able to show that P is a strict subset of EXPTIME.
> So even if an algorithm is EXPTIME-complete, all we can say for sure is that
> it requires more than polynomial time to solve, not that it needs at least
> exponential time.
I thought EXPTIME-complete problems necessarily require
exponential-time. I feel you're making a subtle distinction that I may
not be getting.
<quote src="wikipedia://EXPTIME">
Examples of EXPTIME-complete problems include the problem of looking at
a generalized Chess, Checkers, or Go position, and determining whether
the first player can force a win. These games are EXPTIME-complete
because games can last for a number of moves that is exponential in the
size of the board. (By contrast, generalized games that can last for a
number of moves that is polynomial in the size of the board are often
PSPACE-complete.)
</quote>
Here, even if you can find the solution in polynomial time, the time
needed to write the answer to the tape is exponential to the size of the
board (you have to write every possible sequence of moves and show that
each ends with a win).
> Examples of games that are EXPTIME-complete include chess and checkers .
The quote above states that chess and checkers are not EXPTIME-complete.
The generalized chess and checkers is.
Aziz,,,
Michael N. Christoff
"Abdulaziz Ghuloum" <aghu...@c-s-remove-dashes.indiana.edu> wrote in
message news:chglhc$gcf$1...@hood.uits.indiana.edu...
> Michael N. Christoff wrote:
>
> > "d. lee" <dongh...@hotmail.com> wrote in message
> > news:61d68280.04090...@posting.google.com...
> >
> >>I heared that deciding winner of go-game is in EXPTIME.
> >>Could anyone show me other examples in EXPTIME?
> >>Online list of problems will be helpful.
> >>
> >>Many thanks in advance.
> >
> >
> > I assume by EXPTIME you mean EXPTIME-complete. For example, all O(n)
> > algorithms are EXPTIME since P is in EXPTIME. I'm sure others can fill
in
> > the blanks but: as far as complexity class separations between P, NP and
> > EXPTIME, we've only been able to show that P is a strict subset of
EXPTIME.
> > So even if an algorithm is EXPTIME-complete, all we can say for sure is
that
> > it requires more than polynomial time to solve, not that it needs at
least
> > exponential time.
>
> I thought EXPTIME-complete problems necessarily require
> exponential-time.
>
You're right. My thinking was that the set of all decision problems
solvable in 2^(n^k) time could theoretically be equal to those solvable in
say, 2^(n^(1/k)) time, k > 1, similar to the way P != NP does not imply
NP-complete problems are at least exponential. But the time hierarchy
theorem rules this possibility out for EXPTIME.
------------------
> Examples of games that are EXPTIME-complete include chess and checkers .
The quote above states that chess and checkers are not EXPTIME-complete.
The generalized chess and checkers is.
------------------
I was wondering whether to include the modifier 'generalized', but didn't
since the OP did not.
l8r, Mike N. Christoff
Mike Robson
rules but not known to be if you play Chinese rules.
(The relevant difference concerns multiple ko situations).
Mike Robson.
d. lee
Then, I need to make my question sharper.
1. Is there any obvious problem which is in EXPTIME but not in P?
( besides generalized games)
2. Which text book or internet site describes these problems in detail?
I failed to find one.
(Papadimitriou?)
Mitch Harris
Depends on what you mean by obvious and detail. Yes, Papadimitriou
(Computational Complexity) explains the higher complexity classes (in
chs. 7 and 20). And gives a handful of examples (succinct circuit
value (w/ prf), satisfiability in the Ackermann fragment of FOL
(exactly one universal quantifier (exercise)).
I'm sure there are lots of subfields of logic/algorithms that have
many natural EXPTIME problems, but that involves knowing the specifics
of those subfields.
Check citeseer for more examples?
So my answer to your 2 questions is a qualified yes, succinct circuit
value (qualified because I don't think it is -totally- obvious). I'm
sure there is a better 'canonical' problem to work with, like tiling,
but I can't seem to remember or find a reference.
--
Mitch Harris
(remove q to reply)
d. lee
My aim was to understand examples and their proofs of "not in P"
problems.
I buyed the book of papadimitriou and have read some other books about
complexity theory
(such as Sipser). But still don't know a single proof example of "not
in P" -_-.
My remaining questions are
1. Is there a simple example of "not in P" proof in any problem?
(I know Razborov's restricted arguments on circuit complexity)
2. Exp-complete means automatically "not in P" by time hierachy
theorem?
3. Could you explain what are the CVAL and succinct CVAL problems?
Jamie Andrews; real address @ bottom of message
> My aim was to understand examples and their proofs of "not in P"
> problems.
> I buyed the book of papadimitriou and have read some other books about
> complexity theory
> (such as Sipser). But still don't know a single proof example of "not
> in P" -_-.
> (I know Razborov's restricted arguments on circuit complexity)
How about the problem "PRINT-SUBSETS", for which you are
given a set of n integers, and you have to print all the subsets
of that set of integers?
Theorem: PRINT-SUBSETS is not in P.
Proof: It takes at least 2^n steps to print all the subsets.
Does this not work for some reason?
--Jamie. (a Dover edition designed for years of use!)
andrews .uwo } Merge these two lines to obtain my e-mail address.
@csd .ca } (Unsolicited "bulk" e-mail costs everyone.)
Jym
> My remaining questions are
>
> 1. Is there a simple example of "not in P" proof in any problem?
> (I know Razborov's restricted arguments on circuit complexity)
>
> 2. Exp-complete means automatically "not in P" by time hierachy
> theorem?
Etime != Ptime.
Take the TM that considers its initial tape as an integer n (say,
written in binary), computes 2^n and then write on its tape a string of
2^n 1s.
This cannot be computed in polynomial time because you need exponential
time just to write all the 1s (you can acces only one tape position at a
given time). But it can be computed in exponential time (each operation is
quite easy. If you only have one tape, you'll probably need to go back and
forth between the 1s and the number (2^n) to be decreased each time you
write a 1, but that will just put a quadratic factor on the overall
complexity, thus rising it to something like (2^n)^2, that is 2^(2n),
still exponential.
Anyway, the idea is that Etime != Ptime just because a Etime TM can acces
much more tape positions than a Ptime one.
(that is actually the same idea in proving that Ptime \subset Pspace)
So Etime-complete means not in Ptime.
Notice that this will also give hints for proving "not in P" for some
functions: if you're able to show that the size of the result exponential
in the size of the input, bingo !
(alas, a lot of non-Ptime functions work in small space...)
Hypocoristiquement,
Jym.
tc...@lsa.umich.edu
Jamie Andrews; real address @ bottom of message <m...@privacy.net> wrote:
>In comp.theory d. lee <sci...@gmail.com> wrote:
>> 1. Is there a simple example of "not in P" proof in any problem?
>
>given a set of n integers, and you have to print all the subsets
>of that set of integers?
This works, but is something of a "cheat," because you force exponential
time just by requiring that the output be exponential in length. More
interesting are *decision* problems (whose output is just "yes" or "no")
that provably take exponential time.
And actually, d. lee <sci...@gmail.com> already gave an example, because
certainly by the time hierarchy theorem, any EXPTIME-complete problem is
not in P. "Succinct" problems, as Papadimitriou calls them, are good
examples of problems not in P.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
Mitch Harris
> My remaining questions are
>
> 1. Is there a simple example of "not in P" proof in any problem?
> (I know Razborov's restricted arguments on circuit complexity)
Simple? yeah I agree that the "PRINT SUBSETS" is not fair.
Without looking it up, I wouldn't be surprised if the defs of
-functional- complexity classes also take into account output size.
But I can't think of a simpler example/proof for EXPTIME than
SUCCINCT SAT. (not that it's simple, just that I can't think of one
simpler)
> 2. Exp-complete means automatically "not in P" by time hierachy
> theorem?
yes.
> 3. Could you explain what are the CVAL and succinct CVAL problems?
Papadimitriou, Computational Complexity, p. 492ff, w/ proofs of