En 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 de 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 comprobar si un problema da la respuesta "Sí" o "No".
En el modelo de cálculo del árbol de decisión, la complejidad del certificado es el número mínimo de variables 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 .
La noción de certificado se utiliza para definir la semidecidibilidad : [1] un lenguaje formal L es semidecidible si existe una relación de predicado de dos lugares R ⊆ Σ∗ × Σ∗ tal que R es computable y tal que para todos x ∈ Σ∗:
x ∈ L ⇔ existe y tal que R(x, y)
Los certificados también brindan definiciones para algunas clases de complejidad que, alternativamente, pueden caracterizarse en términos de máquinas de Turing no deterministas . Un lenguaje L está en NP si y solo si existe un polinomio p y una máquina de Turing M acotada en el tiempo polinomial tal que cada palabra x esté en el lenguaje 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 lenguaje tiene un certificado de longitud polinomial, que puede ser verificado por una máquina de Turing determinista limitada por espacio logarítmico que puede leer cada bit del certificado solo una vez. [3] Alternativamente, la máquina de Turing de espacio logarítmico determinista en la declaración anterior puede ser reemplazada por una máquina de Turing de espacio constante probabilística de error acotado a la que se le permite usar solo un número constante de bits aleatorios. [4]
El problema de determinar, para un gráfico dado G y un número k , si el gráfico contiene un conjunto independiente de tamaño k está en NP . Dado un par ( G , k ) en el lenguaje, 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 ). [5]
Un ejemplo más general, para el problema de determinar si una determinada máquina de Turing acepta una entrada en un cierto número de pasos, es el siguiente:
L = {<<M>, x, w> | ¿<M> acepta x en |w| ¿pasos?} Muestre L ∈ NP. verificador: obtiene la cadena c = <M>, 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, <<M>, x, w> ∈ L ⇔ existe c <= a|w| 3 tal que <<M>, x, w, c> ∈ V ∈ P