Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with DLOGTIME:
TR12-186 | 27th December 2012
Andreas Krebs, Nutan Limaye

DLOGTIME-Proof Systems

We define DLOGTIME proof systems, DLTPS, which generalize NC0 proof systems.
It is known that functions such as Exact-k and Majority do not have NC0 proof systems. Here, we give a DLTPS for Exact-k (and therefore for Majority) and also for other natural functions such as Reach and k-Clique. Though ... more >>>

ISSN 1433-8092 | Imprint