Equivalence of measures of complexity classes | Zendy

Josef M. Breutzmann | Zendy; Jack H. Lutz | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Equivalence of measures of complexity classes

Author(s) -

Josef M. Breutzmann,

Jack H. Lutz

Publication year - 1997

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/bfb0023487

Subject(s) - martingale (probability theory) , probability measure , mathematics , martingale difference sequence , equivalence (formal languages) , time complexity , discrete mathematics , bounded function , measure (data warehouse) , complexity class , pspace , probability distribution , algorithm , computational complexity theory , computer science , statistics , data mining , mathematical analysis

The resource-bounded measures of complexity classes are shown to be robust with respect to certain changes in the underlying probability measure. Specifically, for any real number δ > 0, any uniformly polynomial-time computable sequence β=(β0,β1,β2), ... of real numbers (biases) β i e [δ, 1−δ], and any complexity class C (such as P, NP, BPP, P/Poly, PH, PSPACE, etc.) that is closed under positive, polynomial-time, truth-table reductions with queries of at most linear length, it is shown that the following two conditions are equivalent.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research