Uniform normal form for general time-bounded complexity classes

DOI10.1016/0022-0000(86)90034-6zbMath0611.03019OpenAlexW1987141990MaRDI QIDQ1087539

Clement F. Kent, Bernard R. Hodgson

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90034-6

zbMATH Keywords

NPcomplexity hierarchiesarithmetic theory

Mathematics Subject Classification ID

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

Related Items

Diophantine complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets
• Data structures for distributed counting
• An arithmetical characterization of NP
• The polynomial-time hierarchy