An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic | Zendy

Buss Samuel R. | Zendy; Krajíček Jan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research