scientific article; zbMATH DE number 65757

MaRDI QIDQ4010368zbMATH OpenFDO

Authors Pavel Pudlák

Publication date 27 September 1992

zbMATH Keywords

interactive computationsoptimal solutions to optimization problems

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15) Second- and higher-order arithmetic and fragments (03F35)

Recommendations

• scientific article; zbMATH DE number 4213452
• scientific article; zbMATH DE number 65749
• A second order version of S₂ⁱ and U₂¹
• scientific article; zbMATH DE number 218509
• Delineating classes of computational complexity via second order theories with weak set existence principles. I

Cited in

(5)

• Circuit lower bounds in bounded arithmetics
• scientific article; zbMATH DE number 218509 (Why is no real title available?)
• Unprovability of strong complexity lower bounds in bounded arithmetic
• scientific article; zbMATH DE number 4026815 (Why is no real title available?)
• Relating the bounded arithmetic and polynomial time hierarchies

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4010368)