On theories of bounded arithmetic for \(\mathrm{NC}^1\) (Q638497): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:50, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On theories of bounded arithmetic for \(\mathrm{NC}^1\) |
scientific article |
Statements
On theories of bounded arithmetic for \(\mathrm{NC}^1\) (English)
0 references
12 September 2011
0 references
In the paper two theories are introduced: \(\mathrm{VNC}_{*}^{1}\) and its variant \(\overline{\mathrm{VNC}}_{*}^{1}\) -- they correspond to a subclass of \(\mathrm{NC}^{1}\) slightly larger than uniform \(\mathrm{NC}^{1}\). The author works with second-order theories in the spirit of Zambella. The theory \(\mathrm{VNC}_{*}^{1}\) is formulated in the usual language of second-order bounded arithmetic and the theory \(\overline{\mathrm{VNC}}_{*}^{1}\) has a richer language. Basic properties of those theories are proved. A general theorem on conservativity of the axiom of choice over theories meeting certain requirements is also proved. It is shown that propositional translations of \(\Sigma^{B}_{0}\) theorems of \(\overline{\mathrm{VNC}}_{*}^{1}\) have \(L\)-uniform polynomial-size Frege proofs.
0 references
bounded arithmetic
0 references
circuit complexity
0 references
propositional translation
0 references