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

\(P=NP\) problemcomplete setscomputabilityhard setsinitial segmentspolynomial time computationstheory of exponential time

Mathematics Subject Classification ID

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

Review text

The paper is devoted to the study of the P\(=NP\) problem. The theory ET (theory of exponential time) introduced by R. A. DeMillo and R. A. Lipton in 1980 is studied. The author discusses polynomial time computations in models of ET and gives examples of simple functions that are not total in \(M_{D\&L}\vDash ET\) as well as predicates in \(P_{D\&L}\) (a class of predicates over \(M_{D\&L})\) that are not computable in \(M_{D\&L}\). The stronger theory ET(Elem) is introduced and sets that are polynomially computable in some model of ET(Elem) are characterized. The last section of the paper is devoted to the following problem: what types of hard sets have arbitrarily long initial segments that can be efficiently decided by short programs. It is shown that it is easily resolved for P and EXP-time complete sets. The question for NP-complete sets is open.

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

• An arithmetical characterization of NP
• 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?)
• 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)

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

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)