On “provable” analogs of and

DOI10.1007/BF01776574zbMath0405.68046OpenAlexW99744800MaRDI QIDQ4191606

Theodore P. Baker

Publication date: 1979

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01776574

zbMATH Keywords

Turing MachinesComputational ComplexityNp-Complete ProblemsProvability Requirements

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items

Index sets and presentations of complexity classes, Independence results in computer science?

Cites Work

• Optimization Among Provably Equivalent Programs
• Theory of Provable Recursive Functions
• Unnamed Item