ECCC-Report TR05-010https://eccc.weizmann.ac.il/report/2005/010Comments and Revisions published for TR05-010en-usFri, 21 Jan 2005 21:44:07 +0200
Paper TR05-010
| Almost Completeness in Small Complexity Classes |
Olivier Powell
https://eccc.weizmann.ac.il/report/2005/010We constructively prove the existence of almost complete problems under logspace manyone reduction for some small complexity classes by exhibiting a parametrizable construction which yields, when appropriately setting the parameters, an almost complete problem for PSPACE, the class of space efficiently decidable problems, and for SUBEXP, the class of problems decidable in subexponential time. Our construction also implies the existence of almost complete problems under logspace manyone reductions for bigger classes, such as E or EXP. We also investigate almost completeness for smaller time complexity classes, such as P and QP, and clearly identify and explain the reasons (which are not the same for P and QP) why our approach fails for these complexity classes.
Fri, 21 Jan 2005 21:44:07 +0200https://eccc.weizmann.ac.il/report/2005/010