Citation
U. Feige et J. Kilian, ON LIMITED VERSUS POLYNOMIAL NONDETERMINISM, Chicago journal of theoretical computer science, (1), 1997, pp. 1-20
Citations number
25
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
ISSN journal
10730486
Issue
1
Year of publication
1997
Pages
1 - 20
Database
ISI
SICI code
1073-0486(1997):1<1:OLVPN>2.0.ZU;2-Y
Abstract
In this paper, we show that efficient algorithms for some problems tha
t require limited nondeterminism imply the subexponential simulation o
f nondeterministic computation by deterministic computation. In partic
ular, if cliques of size O(log n) can be found in polynomial time, the
n nondeterministic time f(n) is contained in deterministic time 2(O)(r
oot f(n)polylog f(n)).