Existential theory of the reals
http://dbpedia.org/resource/Existential_theory_of_the_reals
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.
rdf:langString
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.
rdf:langString
Экзистенциальная теория вещественных чисел — это множество всех верных утверждений вида где — это , в которую входят равенства и неравенства вещественных многочленов. Задача разрешимости для экзистенциальной теории вещественных чисел — это задача нахождения алгоритма, который решает для каждой формулы, верна она или нет. Эквивалентно, это задача проверки, что заданное полуалгебраическое множество не пусто. Эта задача разрешимости является NP-трудной и лежит в PSPACE. Таким образом, задача имеет существенно меньшую сложность, чем процедура исключения кванторов Альфреда Тарского в теориях первого порядка вещественных. Однако, на практике, общие методы для теории первого порядка остаются предпочтительным выбором для решения такого рода задач.
rdf:langString
rdf:langString
Théorie existentielle sur les réels
rdf:langString
Existential theory of the reals
rdf:langString
Экзистенциальная теория вещественных чисел
xsd:integer
30925590
xsd:integer
1116381351
rdf:langString
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.
rdf:langString
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.
rdf:langString
Экзистенциальная теория вещественных чисел — это множество всех верных утверждений вида где — это , в которую входят равенства и неравенства вещественных многочленов. Задача разрешимости для экзистенциальной теории вещественных чисел — это задача нахождения алгоритма, который решает для каждой формулы, верна она или нет. Эквивалентно, это задача проверки, что заданное полуалгебраическое множество не пусто. Эта задача разрешимости является NP-трудной и лежит в PSPACE. Таким образом, задача имеет существенно меньшую сложность, чем процедура исключения кванторов Альфреда Тарского в теориях первого порядка вещественных. Однако, на практике, общие методы для теории первого порядка остаются предпочтительным выбором для решения такого рода задач. Многие естественные задачи , особенно задачи распознавания геометрических графов пересечений и выпрямления рёбер рисунков графов с пересечениями, могут быть решены путём преобразования их в вариант экзистенциальной теории вещественных чисел и являются для этой теории. Для описания этих задач определяется класс сложности , находящийся между NP и PSPACE .
xsd:nonNegativeInteger
31153