Bounded Width Branching Programs
We examine the branching program model of computation and in particular the classes of languages which can be recognized when the width of the programs is bounded by a constant. After slightly revising the framework of definitions to sharpen analogies with other models, we prove that width 5 polyno...
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149629 |
| _version_ | 1811082921399812096 |
|---|---|
| author | Barrington, David A. |
| author2 | Sipser, Michael |
| author_facet | Sipser, Michael Barrington, David A. |
| author_sort | Barrington, David A. |
| collection | MIT |
| description | We examine the branching program model of computation and in particular the classes of languages which can be recognized when the width of the programs is bounded by a constant. After slightly revising the framework of definitions to sharpen analogies with other models, we prove that width 5 polynomial size branching programs can recognize exactly the parallel complexity class NC1, refuting a conjecture of Borodin et al. in [BDFP83]. |
| first_indexed | 2024-09-23T12:13:23Z |
| id | mit-1721.1/149629 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:13:23Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1496292023-03-30T03:46:03Z Bounded Width Branching Programs Barrington, David A. Sipser, Michael We examine the branching program model of computation and in particular the classes of languages which can be recognized when the width of the programs is bounded by a constant. After slightly revising the framework of definitions to sharpen analogies with other models, we prove that width 5 polynomial size branching programs can recognize exactly the parallel complexity class NC1, refuting a conjecture of Borodin et al. in [BDFP83]. 2023-03-29T15:13:22Z 2023-03-29T15:13:22Z 1986-06 https://hdl.handle.net/1721.1/149629 16963185 MIT-LCS-TR-361 application/pdf |
| spellingShingle | Barrington, David A. Bounded Width Branching Programs |
| title | Bounded Width Branching Programs |
| title_full | Bounded Width Branching Programs |
| title_fullStr | Bounded Width Branching Programs |
| title_full_unstemmed | Bounded Width Branching Programs |
| title_short | Bounded Width Branching Programs |
| title_sort | bounded width branching programs |
| url | https://hdl.handle.net/1721.1/149629 |
| work_keys_str_mv | AT barringtondavida boundedwidthbranchingprograms |