EXPSPACE

EXPSPACE

EXPSPACE

En teoría de la complejidad computacional, la clase de complejidad EXPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2p(n)), donde p(n) es una función polinomial sobre n. (Cuando se restringe p(n) como una función lineal, la clase resultante se denomina ESPACE.)

En términos de DSPACE,

\mbox{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k})

La clase de complejidad EXPSPACE-completo es la clase de los problemas que están en EXPSPACE tales que todo problema de EXPSPACE tiene una transformación polinomial hacia cada uno de los problemas de EXPSPACE-completo. Dicho de otra forma, existe un algoritmo que trabaja en tiempo polinómico que transforma las instancias de un problema en las instancias del otro con la misma respuesta. El conjunto EXPSPACE-completo puede ser visto como el conjunto de los problemas más difíciles de EXPSPACE.

EXPSPACE contiene de forma estricta las clases PSPACE, NP-completo, NP y P y se cree que también contiene estrictamente el conjunto EXPTIME.

Un ejemplo de problema en EXPSPACE-completo es el de decidir si dos expresiones regulares representan lenguajes diferentes, cuando los operadores regulares utilizados son la unión, la concatenación, la clausura de Kleene (cero o más copias de una expresión), y el cuadrado (dos copias de una expresión).

Si no se incluye la clausura de Kleene, el problema es NEXPTIME-completo, que es como EXPTIME-completo, salvo que se define según las máquinas de Turing no-deterministas.

En 1980, L. Berman demostró que el problema de verificar o falsificar cualquier expresión de primer orden sobre los números reales que solo utiliza suma y comparación (pero no multiplicación) está en EXPSPACE.

Referencias

  • L. Berman The complexity of logical theories, Theoretical Computer Science 11:71-78, 1980.
Obtenido de "EXPSPACE"

Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • EXPSPACE — In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) space, where p(n) is a polynomial function of n. (Some authors restrict p(n) to be a linear function, but most authors… …   Wikipedia

  • EXPSPACE — En teoría de la complejidad computacional, la clase de complejidad EXPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2p(n)), donde p(n) es una función polinomial… …   Enciclopedia Universal

  • Spiel-Komplexität — In der kombinatorischen Spieltheorie gibt es mehrere Möglichkeiten die Spiel Komplexität zu messen. Im folgenden werden die folgenden Metriken beschrieben: Zustandsraum Komplexität Spielbaumgröße Entscheidungs Komplexität Spielbaum Komplexität… …   Deutsch Wikipedia

  • PSPACE — Unsolved problems in computer science Is P = PSPACE ? PSPACE …   Wikipedia

  • Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… …   Wikipedia

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

  • Класс EXPTIME — В теории сложности вычислений, класс сложности EXPTIME (иногда называемый просто EXP) это множество задач, решаемых с помощью детерминированной машины Тьюринга за время O(2p(n)), где p(n) это полиномиальная функция о …   Википедия

  • EXPTIME — EXP redirects here; for other uses, see exp. In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2 p ( n )) time, where p ( n… …   Wikipedia

  • DNA computing — is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon based computer technologies. DNA computing, or, more generally, biomolecular computing, is a fast developing interdisciplinary area.… …   Wikipedia

  • NSPACE — In computational complexity theory, the complexity class NSPACE(f(n)) is the set of decision problems that can be solved by a non deterministic Turing machine using space O(f(n)), and unlimited time. It is the non deterministic counterpart of… …   Wikipedia

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”