Polynomial time computations in models of ET

DOI10.1016/0022-0000(83)90004-1MaRDI QIDQ795035zbMATH OpenOpenAlexFDO

Authors 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

complete setscomputabilitypolynomial 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)

Recommendations

• Nondeterministic polynomial-time computations and models of arithmetic
• An overview of computational complexity
• scientific article; zbMATH DE number 4112573
• Publication:3484825
• A foundational delineation of poly-time

Cites work

• scientific article; zbMATH DE number 3693254 (Why is no real title available?)
• scientific article; zbMATH DE number 3758312 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3639601 (Why is no real title available?)
• scientific article; zbMATH DE number 3431764 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• An arithmetical characterization of NP
• Independence results in computer science?
• Indexings of subrecursive classes
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the Structure of Polynomial Time Reducibility
• On the structure of sets in NP and other complexity classes
• Unprovability of theorems of complexity theory in weak number theories

Cited in

(6)

• scientific article; zbMATH DE number 4130016 (Why is no real title available?)
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Nondeterministic polynomial-time computations and models of arithmetic
• Polynomial-time versus recursive models
• scientific article; zbMATH DE number 67686 (Why is no real title available?)
• Complexity of Ehrenfeucht models

This page was built for publication: Polynomial time computations in models of ET

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