Polynomial time computations in models of ET

DOI10.1016/0022-0000(83)90004-1zbMATH Open0542.03019OpenAlexW1985249556MaRDI QIDQ795035FDOQ795035

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

Recommendations

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

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)

Cites Work

• On the Structure of Polynomial Time Reducibility
• Title not available (Why is that?)
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• An arithmetical characterization of NP
• Indexings of subrecursive classes
• Title not available (Why is that?)
• On the structure of sets in NP and other complexity classes
• Independence results in computer science?
• Unprovability of theorems of complexity theory in weak number theories
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (6)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Nondeterministic polynomial-time computations and models of arithmetic
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Polynomial-time versus recursive models
• 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)