Abstract:
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