Skew circuits of small width
A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs – polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known th...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2017
|