ECCC-Report TR03-028https://eccc.weizmann.ac.il/report/2003/028Comments and Revisions published for TR03-028en-usWed, 23 Apr 2003 20:46:25 +0300
Paper TR03-028
| PSPACE contains almost complete problems |
Olivier Powell
https://eccc.weizmann.ac.il/report/2003/028An 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.
Wed, 23 Apr 2003 20:46:25 +0300https://eccc.weizmann.ac.il/report/2003/028