Accessible telephone directories

DOI10.2307/2275252MaRDI QIDQ4292595zbMATH OpenOpenAlexFDO

Authors Bruno Poizat

Publication date 22 January 1995

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2275252

zbMATH Keywords

computation over arbitrary structuresquantifier-elimination

Mathematics Subject Classification ID

Quantifier elimination, model completeness, and related topics (03C10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On relativizations of the P =? NP question for several structures
• scientific article; zbMATH DE number 4049010
• scientific article; zbMATH DE number 3976395
• scientific article; zbMATH DE number 4112573
• scientific article; zbMATH DE number 781350

Cites work

• Des belles paires aux beaux uples

Cited in

(15)

• Universal resolution for NP-complete problems
• Saturation and stability in the theory of computation over the reals
• P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)
• Elimination of constants from machines over algebraically closed fields
• Some aspects of studying an optimization or decision problem in different computational models
• A note on non-complete problems in \(NP_\mathbb{R}\)
• Computational complexity of multi-player evolutionarily stable strategies
• \(\mathbf P =\mathbf{NP}\) for some structures over the binary words
• Two situations with unit-cost: ordered abelian semi-groups and some commutative rings
• On digital nondeterminism
• Safe recursion over an arbitrary structure: PAR, PH and DPH
• Algorithms yield upper bounds in differential algebra
• Calculs sur les structures de langage dénombrable
• A weak version of the Blum, Shub, and Smale model
• Real computational universality: the word problem for a class of groups with infinite presentation

This page was built for publication: Accessible telephone directories

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