Arithmetic theories for computational complexity problems

DOI10.1016/S0019-9958(86)80041-9MaRDI QIDQ3751567zbMATH OpenOpenAlexFDO

Authors Steve Homer, J. Reif

Publication date 1986

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0019-9958(86)80041-9

zbMATH Keywords

polynomial time hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 2196512
• Uniform normal form for general time-bounded complexity classes
• Delineating classes of computational complexity via second order theories with weak set existence principles. I
• scientific article; zbMATH DE number 1542049
• scientific article; zbMATH DE number 1086669

Cited in

(10)

• scientific article; zbMATH DE number 1531922 (Why is no real title available?)
• scientific article; zbMATH DE number 1086669 (Why is no real title available?)
• scientific article; zbMATH DE number 3966052 (Why is no real title available?)
• Nondeterministic polynomial-time computations and models of arithmetic
• scientific article; zbMATH DE number 3931010 (Why is no real title available?)
• scientific article; zbMATH DE number 424614 (Why is no real title available?)
• scientific article; zbMATH DE number 4077311 (Why is no real title available?)
• Uniform normal form for general time-bounded complexity classes
• Index sets and presentations of complexity classes
• Integer complexity: algorithms and computational results

This page was built for publication: Arithmetic theories for computational complexity problems

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