CJTCS Volume 1997 Article 1

On Limited versus Polynomial Nondeterminism

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

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


[] Volume 1996, Article 6 [] Article 2
[back] Volume 1997 [back] Published articles
[CJCTS home]

Last modified: 2 June 1997