Abstract
Article Bounded-width polynomial-size branching programs recognize exactly those languages in NC1 Share on Author: D A Barrington Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 1–5https://doi.org/10.1145/12130.12131Online:01 November 1986Publication History 113citation1,087DownloadsMetricsTotal Citations113Total Downloads1,087Last 12 Months19Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Keywords
CitationBounded functionBranching (polymer chemistry)Computer scienceDiscrete mathematicsCombinatoricsMathematicsWorld Wide Web
Affiliated Institutions
Related Publications
Neo
Article Free Access Share on Neo: learning conceptual knowledge by sensorimotor interaction with an environment Authors: Paul R. Cohen Experimental Knowledge Systems Laboratory,...
Observations on the dynamics of a congestion control algorithm
Article Free Access Share on Observations on the dynamics of a congestion control algorithm: the effects of two-way traffic Authors: Lixia Zhang Computer Science Laboratory, Xer...
A control-theoretic approach to flow control
article Free Access Share on A control-theoretic approach to flow control Author: Srinivasan Keshav Computer Science Division, Department of EECS, University of California, Berk...
Publication Info
- Year
- 1986
- Type
- article
- Pages
- 1-5
- Citations
- 681
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
681
OpenAlex
Cite This
David A. Mix Barrington
(1986).
Bounded-width polynomial-size branching programs recognize exactly those languages in <i>NC</i><sup>1</sup>.
, 1-5.
https://doi.org/10.1145/12130.12131
Identifiers
- DOI
- 10.1145/12130.12131