Premium
An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
Author(s) -
Buss Samuel R.,
Krajíček Jan
Publication year - 1994
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/s3-69.1.1
Subject(s) - mathematics , bounded function , independence (probability theory) , polynomial , discrete mathematics , separation (statistics) , arithmetic , combinatorics , statistics , mathematical analysis
We develop a method for establishing the independence of some∑ i b( α )formulas fromS 2 i( α ). In particular, we show thatT 2 i( α )is not ∀ ∑ 2 i( α )‐conservative overS 2 i( α ). We characterize the∑ i b‐definable functions ofT 2 1as being precisely the functions definable as projections of polynomial local search (PLS) problems.