An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form where the variables are interpreted as having real number values, and where is a quantifier-free formula involving equalities and inequalities of real polynomials. A sentence of this form is true if it is possible to find values for all of the variables that, when substituted into formula , make it become true.

Property Value
dbo:abstract
  • In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form where the variables are interpreted as having real number values, and where is a quantifier-free formula involving equalities and inequalities of real polynomials. A sentence of this form is true if it is possible to find values for all of the variables that, when substituted into formula , make it become true. The decision problem for the existential theory of the reals is the problem of finding an algorithm that decides, for each such sentence, whether it is true or false. Equivalently, it is the problem of testing whether a given semialgebraic set is non-empty. This decision problem is NP-hard and lies in PSPACE. Thus it has significantly lower complexity than Alfred Tarski's quantifier elimination procedure for deciding statements in the first-order theory of the reals without the restriction to existential quantifiers. However, in practice, general methods for the first-order theory remain the preferred choice for solving these problems. Many natural problems in geometric graph theory, especially problems of recognizing geometric intersection graphs and straightening the edges of graph drawings with crossings, may be solved by translating them into instances of the existential theory of the reals, and are complete for this theory. The complexity class , which lies between NP and PSPACE, has been defined to describe this class of problems. (en)
  • En logique mathématique, la théorie existentielle sur les réels est l'ensemble des formules existentielles de la logique premier ordre vraies sur les réels. Elle est intéressante pour la planification de mouvement de robots. Elle est décidable et NP-dure et dans PSPACE. Elle définit aussi une classe de complexité entre NP et PSPACE, notée , pour laquelle des problèmes géométriques sur les graphes sont complets. (fr)
  • Экзистенциальная теория вещественных чисел — это множество всех верных утверждений вида где — это , в которую входят равенства и неравенства вещественных многочленов. Задача разрешимости для экзистенциальной теории вещественных чисел — это задача нахождения алгоритма, который решает для каждой формулы, верна она или нет. Эквивалентно, это задача проверки, что заданное полуалгебраическое множество не пусто. Эта задача разрешимости является NP-трудной и лежит в PSPACE. Таким образом, задача имеет существенно меньшую сложность, чем процедура исключения кванторов Альфреда Тарского в теориях первого порядка вещественных. Однако, на практике, общие методы для теории первого порядка остаются предпочтительным выбором для решения такого рода задач. Многие естественные задачи , особенно задачи распознавания геометрических графов пересечений и выпрямления рёбер рисунков графов с пересечениями, могут быть решены путём преобразования их в вариант экзистенциальной теории вещественных чисел и являются для этой теории. Для описания этих задач определяется класс сложности , находящийся между NP и PSPACE . (ru)
dbo:wikiPageID
  • 30925590 (xsd:integer)
dbo:wikiPageLength
  • 31153 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1116381351 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • En logique mathématique, la théorie existentielle sur les réels est l'ensemble des formules existentielles de la logique premier ordre vraies sur les réels. Elle est intéressante pour la planification de mouvement de robots. Elle est décidable et NP-dure et dans PSPACE. Elle définit aussi une classe de complexité entre NP et PSPACE, notée , pour laquelle des problèmes géométriques sur les graphes sont complets. (fr)
  • In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form where the variables are interpreted as having real number values, and where is a quantifier-free formula involving equalities and inequalities of real polynomials. A sentence of this form is true if it is possible to find values for all of the variables that, when substituted into formula , make it become true. (en)
  • Экзистенциальная теория вещественных чисел — это множество всех верных утверждений вида где — это , в которую входят равенства и неравенства вещественных многочленов. Задача разрешимости для экзистенциальной теории вещественных чисел — это задача нахождения алгоритма, который решает для каждой формулы, верна она или нет. Эквивалентно, это задача проверки, что заданное полуалгебраическое множество не пусто. Эта задача разрешимости является NP-трудной и лежит в PSPACE. Таким образом, задача имеет существенно меньшую сложность, чем процедура исключения кванторов Альфреда Тарского в теориях первого порядка вещественных. Однако, на практике, общие методы для теории первого порядка остаются предпочтительным выбором для решения такого рода задач. (ru)
rdfs:label
  • Théorie existentielle sur les réels (fr)
  • Existential theory of the reals (en)
  • Экзистенциальная теория вещественных чисел (ru)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License