Polynomial time computations in models of ET

DOI10.1016/0022-0000(83)90004-1zbMath0542.03019OpenAlexW1985249556MaRDI QIDQ795035

Deborah Joseph

Publication date: 1983

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

Full work available at URL: https://hdl.handle.net/1813/6340

zbMATH Keywords

computabilitycomplete setspolynomial time computations\(P=NP\) problemhard setsinitial segmentstheory of exponential time

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Nonstandard models of arithmetic (03H15)

Related Items

Some remarks on witness functions for nonpolynomial and noncomplete sets in NP

Cites Work

• Indexings of subrecursive classes
• Independence results in computer science?
• Unprovability of theorems of complexity theory in weak number theories
• On the structure of sets in NP and other complexity classes
• An arithmetical characterization of NP
• On the Structure of Polynomial Time Reducibility
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item