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

• Preformatted versions of the article
  • DVI (71,336 bytes)
  • PostScript (260,574 bytes)
  • PDF (250,579 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX ( cj97-01.tex , 50,547 bytes)
  • BIBTeX ( cj97-01.bib , 8,782 bytes)
  • Parameter settings for custom formatting ( cjropts.tex , 164 bytes)
  • Self citation in BIBTeX (261 bytes)
• Online discussion
• Instructions for Readers

---

Volume 1996, Article 6 Article 2
Volume 1997 Published articles

Last modified: 2 June 1997