La versión NP del teorema de Matiyasevich

Question

Por Matiyasevich, para cada recursivamente enumerable set $A$ de los números naturales existe un polinomio $f(x_1,...,x_n)$ con coeficientes enteros tales que para cada $p\ge 0$, $f(x_1,...,x_n)=p$ ha entero soluciones si y sólo si $p\in A$.

Ahora supongamos que $A$ es un conjunto de números naturales con la pertenencia problema en $NP$. Existe un polinomio $f$ con coeficientes enteros tales que $f(x_1,...,x_n)=p$ ha entero soluciones si y sólo si $p\in A$ y no existe una solución con $||x_i||\le Cp^s$ para algunos fijos $s, C$ donde $||x_i||$ es la longitud de $x_i$ en binario (es decir,$\sim \log |x_i|$)? Claramente lo contrario también es cierto: si un polinomio existe, entonces la membresía problema para $A$ está en NP.

Answer 1

Yo no sé acerca de la forma particular del polinomio que se usa, pero en general, es un conocido problema abierto si todos NP puede ser representada por una ecuación de Diophantine con un polinomio límite en la longitud de las soluciones. Adleman y Manders demostrado que el conjunto de $\{\langle a,b,c\rangle\in\mathbb N^3:(\exists x,y\in\mathbb N)(ax^2+by=c)\}$ es NP-completo, por lo tanto la respuesta es positiva iff la clase de tales representable conjuntos es cerrado bajo polinomio reducciones en el tiempo, pero no está claro si éste es realmente cierto o no. Ver la introducción de Pollett para un resumen de algunos resultados parciales.

Answer 2

Creo que este es todavía un problema abierto. La idea de un No-Determinista Diophantine de la Máquina (NDDM) fue introducido por Adleman y Manders. En su papel de Diophantine Complejidad, se conjetura que la clase de problemas reconocibles en el polinomio en el tiempo por un NDDM son, precisamente, los problemas en NP. Sin embargo, únicamente resultan los siguientes:

1. Si es aceptado en un NDDM en el tiempo $T$, entonces se acepta en NDTM en el tiempo $T^2$.
2. Si se acepta en NDTM en el tiempo $T$, entonces a es aceptado en un NDDM en el tiempo $2^{10T^2}$.

También para mostrar que si R₀ es el problema de determinar si todos los bits de un número natural son cero, entonces R₀ es reconocido en el polinomio en el tiempo por un NDDM si y sólo si todos los problemas NP son reconocidos en el polinomio en el tiempo por un NDDM.

PS: Técnicamente hablando, un NDDM no es exactamente del tipo que usted pide en su pregunta. Sin embargo, uno recupera la forma que deseas utilizar Putnam truco: las ecuaciones $P(x,x_1,\ldots,x_n) = 0$ e $x = x(1 - P(x,x_1,\ldots,x_n)^2)$ tienen exactamente las mismas soluciones.