Para mostrar que un problema de decisión dado * [matemática] A [/ matemática] es [matemática] \ mathbf {NP} [/ matemática] -duro, usted toma un problema arbitrario [matemática] B \ in \ mathbf {NP} [/ matemática], que por definición significa que debe existir un verificador de tiempo polinomial ** Máquina de Turing [matemática] V [/ matemática] para [matemática] B [/ matemática] – y usted demuestra que el polinomio [matemático] B [/ matemático] -tiempo se reduce a [matemática] A [/ matemática], utilizando solo la suposición de que [matemática] V [/ matemática] existe.
Un ejemplo “prototípico” es la satisfacción del circuito booleano, también conocido como CSAT. Una prueba de que CSAT es [math] \ mathbf {NP} [/ math] -hard especifica una reducción que convierte la instancia [math] x [/ math] de [math] B [/ math] en un circuito booleano que simula [math ] V [/ math], con la instancia [math] x [/ math] “cableada” en el circuito y las entradas abiertas restantes del circuito destinadas a aceptar un certificado para [math] x [/ math] (usted puede usar la complejidad temporal de [math] V [/ math] y la longitud de [math] x [/ math] para vincular el número de entradas que necesita proporcionar en el circuito). El circuito simula [matemática] V [/ matemática] en [matemática] x [/ matemática] en el sentido de que las entradas [matemática] c_1, c_2,…, c_k [/ matemática] satisfacen el circuito si y solo si [ matemática] V (x, c) [/ matemática] genera “sí”, donde [matemática] c = c_1c_2 … c_k [/ matemática] es la concatenación de dichas entradas de circuito.
Vale la pena buscar los detalles de cómo codificar, por ejemplo, una máquina de Turing como un circuito booleano (es básicamente el contenido del Teorema de Cook-Levin, que dio origen a la teoría de [math] \ mathbf {NP} [/ math] -hardness ), pero incluso sabiendo intuitivamente que prácticamente implementamos todos nuestros dispositivos informáticos utilizando tecnología de circuito booleano debería proporcionarle alguna evidencia de que todo esto se puede hacer.
* Un problema de decisión es cualquier problema donde la solución que estamos buscando es simplemente un “sí” o un “no”. La investigación de trazabilidad computacional generalmente se enfoca en problemas de decisión por conveniencia, pero cualquier problema más general puede ser “refundido” como un problema de decisión adecuado.
** Un verificador [matemático] V [/ matemático] problema [matemático] B [/ matemático] es una máquina de Turing tal que para cualquier caso [matemático] x [/ matemático] del problema [matemático] B [/ matemático], [ math] x [/ math] es una instancia de “sí” si y solo si existe alguna información [math] c [/ math], conocida como certificado para [math] x [/ math], de modo que [math] V (x, c) [/ math] genera “sí”.
- ¿Hay algún problema que requiera más tiempo exponencial de resolución (por ejemplo, doble exp.) Pero que pueda verificarse en tiempo polinómico determinista?
- ¿Hay ejemplos fractales que usen entradas aleatorias externas de alguna manera en las iteraciones?
- ¿Puedo usar una función hash para ordenar registros de manera aleatoria pero consistente?
- Informática: ¿Son nerds los estudiantes de informática?
- ¿Cuál es el algoritmo para encontrar todas las soluciones de hacer 100 de 1-2-3-4-5-6-7-8-9 en orden?
