Arithmetic theories for computational complexity problems

DOI10.1016/S0019-9958(86)80041-9zbMATH Open0611.03018OpenAlexW1994197129MaRDI QIDQ3751567FDOQ3751567

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

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

zbMATH Keywords

polynomial time hierarchy

Mathematics Subject Classification ID

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

Cited In (10)

• Uniform normal form for general time-bounded complexity classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Integer complexity: algorithms and computational results
• Nondeterministic polynomial-time computations and models of arithmetic
• Index sets and presentations of complexity classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)