Circuits in bounded arithmetic.
Item
-
Title
-
Circuits in bounded arithmetic.
-
Identifier
-
AAI9130348
-
identifier
-
9130348
-
Creator
-
Mantzivis, Georgios Spyridon.
-
Contributor
-
Adviser: Attila Mate
-
Date
-
1991
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Mathematics | Computer Science
-
Abstract
-
We employ elementary combinatorial and circuit theoretic arguments to show that if {dollar}Q(x){dollar} is a predicate from any of the classes {dollar}{lcub}\cal SB{rcub}\sbsp{lcub}1{rcub}{lcub}\rm N{rcub}{dollar}, {dollar}{lcub}\cal SB{rcub}\sbsp{lcub}1{rcub}{lcub}\rm N{rcub}{dollar}(BIT), {dollar}{lcub}\cal SB{rcub}\sbsp{lcub}1{rcub}{lcub}\rm N{rcub}{dollar}(BIT, CARD), {dollar}{lcub}\cal SB{rcub}\sbsp{lcub}1{rcub}{lcub}\rm N{rcub}{dollar}(trunc), {dollar}{lcub}\cal SB{rcub}\sbsp{lcub}1{rcub}{lcub}\rm N{rcub}{dollar}(trunc, CARD), and {dollar}{lcub}\cal SB{rcub}\sbsp{lcub}1{rcub}{lcub}\rm N{rcub}{dollar}(trunc, flip) then there is a nontrivial domain in which {dollar}Q(x){dollar} can be calculated by bounded depth and polynomial size circuitry.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
