Re: examples of EXPTIME

tchow_at_lsa.umich.edu
Date: 10/06/04 

Date: 06 Oct 2004 18:52:10 GMT

In article <2siqb7F1le0pmU2@uni-berlin.de>,
Jamie Andrews; real address @ bottom of message <me@privacy.net> wrote:
>In comp.theory d. lee <scikid@gmail.com> wrote:
>> 1. Is there a simple example of "not in P" proof in any problem?
>
> 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?

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 <scikid@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

Relevant Pages

  • Re: Discussion: rmgroup comp.software.year-2000
    ... Jamie Andrews; real address @ bottom of message ... news:comp.software.year-2000.tech needs similar treatment; I suspect ...
    (comp.programming)
  • Re: Discussion: rmgroup comp.software.year-2000
    ... Jamie Andrews; real address @ bottom of message ... news:comp.software.year-2000.tech needs similar treatment; I suspect ...
    (comp.lang.cobol)
  • Re: unions between elves and men
    ... Jamie Andrews; real address @ bottom of message wrote: ... Prev by Date: ...
    (rec.arts.books.tolkien)
  • Spector trial: Henry Lee bails
    ... Lee says, "The bottom line is I did not take a fingernail," ... evidence from the crime scene, ... "I'm off to China," Lee said in a telephone interview from an airport ... "The bottom line is I did not take a fingernail," he said. ...
    (alt.true-crime)
  • Re: Spector trial: Henry Lee bails
    ... Lee says, "The bottom line is I did not take a fingernail," ... evidence from the crime scene, ... "I'm off to China," Lee said in a telephone interview from an airport ... "The bottom line is I did not take a fingernail," he said. ...
    (alt.true-crime)