Isolation, matching, and counting uniform and nonuniform upper bounds

Eric Allender, Klaus Reinhardt, Shiyu Zhou

Research output: Contribution to journalConference articlepeer-review

57 Scopus citations

Abstract

We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar techniques, we show that counting the number of accepting paths of a nondeterministic logspace machine can be done in NL/poly, if the number of paths is small. This clarifies the complexity of the class FewL. Using derandomization techniques, we then improve this to show that this counting problem is in NL. Determining if our other theorems hold in the uniform setting remains an important open question, although we provide evidence that they do. More precisely, if there are problems in DSPACE(n) requiring exponential-size circuits, then all of our results hold in the uniform setting.

Original languageEnglish (US)
Pages (from-to)164-181
Number of pages18
JournalJournal of Computer and System Sciences
Volume59
Issue number2
DOIs
StatePublished - Oct 1999
EventProceedings of the 1998 13th Annual IEEE Conference on Computation Complexity - Buffalo, NY, USA
Duration: Jun 15 1998Jun 18 1998

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Isolation, matching, and counting uniform and nonuniform upper bounds'. Together they form a unique fingerprint.

Cite this