
On limited versus polynomial nondeterminism
Uriel Feige? Joe Kiliany
December 5, 1995
Abstract
We show that efficient algorithms for some problems that require limited nondeterminism imply 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
2O(pf(n) polylog f(n) ).
1 Introduction
A major open question in computational complexity is whether P = NP . Put in other words, is it true that if a language L can be recognized in time f(n) by a nondeterministic Turing machine (where n denotes the input length), then L can be recognized in time (f(n))c by a deterministic Turing machine (for some constant c)? Let DTIME(f(n)) denote the class of languages accepted by a deterministic Turing machine in time O(f(n)), and let NTIME(f(n)) denote the class of languages accepted by a deterministic Turing machine in time O(f(n)). The trivial relations between these classes are DTIME(f(n)) ae NTIME(f(n)) (by definition), and NTIME(f(n)) ae DTIME(2O(f(n))) (by exhaustive search). Perhaps the only nontrivial relation known is that DTIME(n) <> NTIME(n) [16].
A natural question to ask is whether there is a general methodology that improves over exhaustive search, and applies to a wide range of NPproblems. For some specific NP problems, improvements over exhaustive search that involve the constant in the exponent were obtained in [23, 22, 4]. However, we seek a more dramatic improvement, with more general applicability. This leads to the following question:
?Department of Applied Math and Computer Science, the Weizmann Institute, Rehovot 76100, Israel.
feige@wisdom.weizmann.ac.il. Incumbent of the Joseph and Celia Reskin Career Development Chair.
Supported by a Yigal Alon fellowship. Work done in part while the author was visiting the NEC Research
Institute.
yNEC Research Institute, 4 Independence Way, Princeton, New Jersey, 08540. joe@research.nj.nec.com