Chicago Journal of Theoretical Computer Science

Volume 1997

Article 1

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.

On Limited versus Polynomial Nondeterminism

Uriel Feige (Weizmann Institute) and Joe Kilian (NEC Research Institute)
12 March 1997

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)})}.

DOI: 10.4086/cjtcs.1997.001
[] Volume 1996, Article 6 [] Article 2
[back] Volume 1997 [back] Published articles
[CJCTS home]

Last modified: 2 June 1997