En la teoría de la complejidad computacional , un certificado (también llamado testigo ) es una cadena que certifica la respuesta a un cálculo o certifica la pertenencia a alguna cadena en un idioma. A menudo se piensa en un certificado como una ruta de solución dentro de un proceso de verificación, que se utiliza para verificar si un problema da la respuesta "Sí" o "No".
En el modelo de cálculo de árbol de decisión , la complejidad del certificado es el número mínimo devariables de entrada de un árbol de decisión a las que se debe asignar un valor para establecer definitivamente el valor de la función booleana .
Usar en definiciones
La noción de certificado se usa para definir semidecidibilidad : [1] L es semidecidible si hay un predicado de dos lugares R ⊆ Σ ∗ × Σ ∗ tal que R es computable, y tal que para todo x ∈ Σ ∗ :
x ∈ L ⇔ existe y tal que R (x, y)
Los certificados también dan definiciones para algunas clases de complejidad que, alternativamente, pueden caracterizarse en términos de máquinas de Turing no deterministas . Una lengua L está en NP si y sólo si existe un polinomio py una máquina de Turing acotada en tiempo polinomial M tal que cada palabra x está en la lengua L precisamente si existe un certificado c de longitud como máximo p (| x | ) tal que M acepta el par ( x , c ). [2] La clase co-NP tiene una definición similar, excepto que hay certificados para las palabras que no están en el idioma.
La clase NL tiene una definición de certificado: un problema en el idioma tiene un certificado de longitud polinomial, que puede ser verificado por una máquina de Turing delimitada por espacios logarítmicos determinista que puede leer cada bit del certificado una sola vez. [3]
Ejemplos de
El problema de determinar, para una gráfica G y un número k dados , si la gráfica contiene un conjunto independiente de tamaño k está en NP . Dado un par ( G , k ) en el idioma, un certificado es un conjunto de k vértices que no son adyacentes por pares (y por lo tanto son un conjunto independiente de tamaño k ). [4]
Un ejemplo más general, para el problema de determinar si una máquina de Turing dada acepta una entrada en un cierto número de pasos, es el siguiente:
L = {<, x, w> | acepta x en | w | ¿pasos?} Muestre L ∈ NP. verificador: obtiene la cadena c =, x, w tal que | c | <= P (| w |) compruebe si c es un cálculo aceptable de M en x con como máximo | w | pasos | c | <= O (| w | 3 ) si tenemos un cálculo de una TM con k pasos, el tamaño total de la cadena de cálculo es k 2 Por lo tanto, <, x, w> ∈ L ⇔ existe c <= a | w | 3 tal que <, x, w, c> ∈ V ∈ P
Ver también
- Testigo (matemáticas) , un concepto análogo en lógica matemática
Referencias
- ^ Cook, Stephen. "Computabilidad y no computabilidad" (PDF) . Consultado el 7 de febrero de 2013 .
- ^ Arora, Sanjeev; Barak, Boaz (2009). "Definición 2.1". Teoría de la complejidad: un enfoque moderno . Prensa de la Universidad de Cambridge. ISBN 978-0-521-42426-4.
- ^ Arora, Sanjeev; Barak, Boaz (2009). "Definición 4.19". Teoría de la complejidad: un enfoque moderno . Prensa de la Universidad de Cambridge. ISBN 978-0-521-42426-4.
- ^ Arora, Sanjeev; Barak, Boaz (2009). "Ejemplo 2.2". Teoría de la complejidad: un enfoque moderno . Prensa de la Universidad de Cambridge. ISBN 978-0-521-42426-4.
enlaces externos
- Buhrman, Harry; de Wolf, Ronald (2002), Medidas de complejidad y complejidad del árbol de decisión: una encuesta.
- Complejidad computacional: un enfoque moderno de Sanjeev Arora y Boaz Barak