scientific article; zbMATH DE number 781350

zbMath0832.68044MaRDI QIDQ4841154

Bruno Poizat

Publication date: 1 August 1995

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

algorithmquantifier eliminationBoolean equationsBoolean circuit

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantifier elimination, model completeness, and related topics (03C10)

Related Items (27)

Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries ⋮ On the expressiveness and decidability of o-minimal hybrid systems ⋮ Two situations with unit-cost: ordered abelian semi-groups and some commutative rings ⋮ Elimination of constants from machines over algebraically closed fields ⋮ Universal resolution for NP-complete problems ⋮ Computation over algebraic structures and a classification of undecidable problems ⋮ Interpolation in Valiant's theory ⋮ A note on non-complete problems in \(NP_\mathbb{R}\) ⋮ Universal relations and {\#}P-completeness ⋮ Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH ⋮ On Relativizations of the P =? NP Question for Several Structures ⋮ Partially definable forcing and bounded arithmetic ⋮ \(\text{P}\neq \text{NP}\) for the reals with various analytic functions ⋮ Implicit complexity over an arbitrary structure: Quantifier alternations ⋮ Weak arithmetics ⋮ Weak arithmetic ⋮ The P-DNP problem for infinite Abelian groups ⋮ Calculs sur les structures de langage dénombrable ⋮ Real computational universality: the word problem for a class of groups with infinite presentation ⋮ VPSPACE and a transfer theorem over the complex field ⋮ Elimination of parameters in the polynomial hierarchy ⋮ Isomorphism theorem for BSS recursively enumerable sets over real closed fields ⋮ Some aspects of studying an optimization or decision problem in different computational models ⋮ Saturation and stability in the theory of computation over the reals ⋮ Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions ⋮ A Survey on Analog Models of Computation ⋮ On the computational structure of the connected components of a hard problem

This page was built for publication: