Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-028 | 28th February 2003 00:00

PSPACE contains almost complete problems


Authors: Olivier Powell
Publication: 23rd April 2003 20:46
Downloads: 1629


An almost complete set A for a complexity class C is a language of C which is not complete, but that has the property that ``many'' languages of C reduce to A, where the term ``many'' is used in reference to Lutz's resource bounded measure (rbm). The question of the existence of almost complete sets is unanswered for small complexity classes, which are those that do not or are not known to contain ETIME=time(2^O(n)).
One of the reasons for the emptiness of quantitative-completeness results for small complexity class, as opposed to the case of big complexity classes, where such results are abundant, is the fact that Lutz's rbm does not work well for small classes. We use a variation of Lutz's rbm designed to work for small complexity, and use a diagonalisation process to prove that there exists a problem which is almost complete for PSPACE, the class of space efficiently decidable problems.

ISSN 1433-8092 | Imprint