Published by MIT Press. Copyright 1997 Massachusetts Institute of Technology.
Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.
In this paper, we show that efficient algorithms for some problems that require limited nondeterminism imply the subexponential simulation of nondeterministic computation by deterministic computation. In particular, if cliques of size O(log n) can be found in polynomial time, then nondeterministic time f(n) is contained in deterministic time 2^{O(\sqrt{f(n)polylog f(n)})}.
Last modified: 2 June 1997