18 Sep 2000 harrisj   » (Master)

Pseudonym: Thanks for your answer. You are a veritable font of knowledge on the subject. I'm quite impressed.

I'm a bit rusty from when I took a class on theoretical computer science a few years back. Can you perhaps briefly describe some of the more interesting properties of EXPTIME. I'm particularly interested in verification time vs. calculation time. For instance, I know that an NP-time problem can be verified in P-time (I think this has been proven). Is this also true of EXPTIME problems, or is verification in a higher class, or is it simply unprovable.

EXPTIME measures execution in time, EXPSPACE measures execution in space. It is known that EXPTIME is a subset of EXPSPACE, but not known whether it is proper containment or not (all we know is that P != EXPTIME, right?). This is correct. I'm still trying to get an idea of what the "meaning" of EXPTIME is. Mainly, what is an example EXPTIME algorithm?

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!