A syntactical definition of the problem

DOI10.1080/00207168508803464MaRDI QIDQ3741055zbMATH OpenOpenAlexFDO

Authors Amihood Amir, Yaacov Choueka

Publication date 1985

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207168508803464

zbMATH Keywords

deterministic machinesequivalence problem of two languagesloop-programsnondeterministic machinesPL-programspolynomially computable functionsTuring Machines

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• To the problem P=?NP
• scientific article; zbMATH DE number 139620
• P, NP, and the Post correspondence problem
• Nondeterminism within $P^ * $
• scientific article; zbMATH DE number 176517

Cites work

• Loop-programs and polynomially computable functions
• Polynomial computations in non-deterministic loop-programs and PL-programs

Cited in

(8)

• An inductive number-theoretic characterization of NP
• Super-exponentials nonprimitive recursive, but rudimentary
• To the problem P=?NP
• \(\mathbf P =\mathbf{NP}\) for some structures over the binary words
• A Simple P-Complete Problem and Its Representations by Language Equations
• scientific article; zbMATH DE number 139620 (Why is no real title available?)
• scientific article; zbMATH DE number 6950175 (Why is no real title available?)
• A simple P-complete problem and its language-theoretic representations

This page was built for publication: A syntactical definition of the problem

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