Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VALIANT-VAZIRANI LEMMA:
Reports tagged with Valiant-Vazirani Lemma:
TR08-063 | 21st April 2008
Müller Moritz

Valiant-Vazirani Lemmata for Various Logics

We show analogues of a theorem due to Valiant and Vazirani
for intractable parameterized complexity classes such as W[P], W[SAT]
and the classes of the W-hierarchy as well as those of the A-hierarchy.
We do so by proving a general ``logical'' version of it which may be of
independent interest

... more >>>



ISSN 1433-8092 | Imprint