P-Uniform Circuit Complexity

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

Much complexity-theoretic work on parallelism has focused on the class NC, which is defined in terms of logspace-uniform circuits. Yet P-uniform circuit complexity is in some ways a more natural setting for studying feasible parallelism. In this paper, P-uniform NC 1989 is characterized in terms of space-bounded AuxPDAs and alternating Turing Machines with bounded access to the input. The notions of general-purpose and special-purpose computation are considered, and a general-purpose parallel computer for PUNC is presented. It is also shown that NC = PUNC if all tally languages in P are in NC; this implies that the NC = PUNC question and the NC = P question are both instances of the ASPACE(S(n)) = ASPACE,TIME(S(n), S(n)o(1)) question. As a corollary, it follows that NC = PUNC implies PSPACE = DTIME(2no(1)).

Original languageEnglish (US)
Pages (from-to)912-928
Number of pages17
JournalJournal of the ACM (JACM)
Volume36
Issue number4
DOIs
StatePublished - Jan 10 1989

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'P-Uniform Circuit Complexity'. Together they form a unique fingerprint.

Cite this