On the amount of nondeterminism and the power of verifying

1993, Springer Verlag. All rights reserved. The relationship between nondeterminism and other computational resources is studied based on a special interactive-proof system model GC. Let s(n) be a function and C be a complexity class. Define GC(s(n), C) to be the class of languages that are accepted by verifiers in C that can make an extra O(s(n)) amount of nondeterminism. Our main results are (1) A systematic technique is developed to show that for many functions s(n) and for many complexity classes C, the class GC(s(n),C) has natural complete languages; (2) The class 0h of languages accepted by log-time alternating Turing machines making h alternations is precisely the class of languages accepted by uniform families of circuits of depth h; (3) The classes GC(s(n),0h h1, characterize precisely the fixed-parameter intractability of NP-hard optimization problems. In particular, the (2h)th level W[2h] of W-hierarchy introduced by Downey and Fellows collapses if and only if GC(s(n), 02h) P for some s(n) = (log n).

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

On the amount of nondeterminism and the power of verifying Conference Paper