Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR03-029 | 1st April 2003
Philippe Moser

BPP has effective dimension at most 1/2 unless BPP=EXP

We prove that BPP has Lutz's p-dimension at most 1/2 unless BPP equals EXP.
Next we show that BPP has Lutz's p-dimension zero unless BPP equals EXP
on infinitely many input lengths.
We also prove that BPP has measure zero in the smaller complexity
class ... more >>>


TR03-028 | 28th February 2003
Olivier Powell

PSPACE contains almost complete problems

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 ... more >>>


TR03-027 | 21st April 2003
Christian Glaßer, Alan L. Selman, Samik Sengupta

Reductions between Disjoint NP-Pairs

We prove that all of the following assertions are equivalent:
There is a many-one complete disjoint NP-pair;
there is a strongly many-one complete disjoint NP-pair;
there is a Turing complete disjoint NP-pair such that all reductions
are smart reductions;
there is a complete disjoint NP-pair for one-to-one, invertible ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint