¿Hay un problema natural en los productos naturales que es NP-completo?

30

Cualquier número natural puede considerarse como una secuencia de bits, por lo que ingresar un número natural es lo mismo que ingresar una secuencia 0-1, por lo que obviamente existen problemas de NP completo con entradas naturales. Pero, ¿hay algún problema natural, es decir, uno que no utilice codificación e interpretación especial de los dígitos? Por ejemplo "Is na prime?" es un problema tan natural, pero este está en P. O "¿Quién gana el juego Nim con montones de tamaño 3, 5, n, n?" Es otro problema que considero natural, pero también sabemos que está en P. También estoy interesado en otras clases de complejidad en lugar de NP.

Actualización: Como señaló Emil Jeřábek, dado $a,b,c\in \mathbb N,$ para determinar si $ax^2+by-c=0$ tiene una solución sobre los naturales es NP-completo. Esto es exactamente lo que tenía en mente como natural, excepto que aquí la entrada es tres números en lugar de solo uno.

Actualización 2: Y después de más de cuatro años de espera, Dan Brumleve ha dado una "mejor" solución: tenga en cuenta que todavía no está completa debido a la reducción aleatoria.

cc.complexity-theory np-hardness nt.number-theory combinatorial-game-theory domotorp
fuente

1

Sé de un problema de mosaico completo NEXP donde la entrada es un entero ny el problema es determinar si existe un mosaico válido de una cuadrícula nxn. Si eso es interesante para ti, buscaré el periódico.

Robin Kothari

2

@Emil: el comentario de domotorp fue una respuesta a una confusión que tuve. Pero fue un malentendido de mi parte, así que borré el comentario. Creo que la entrada debe ser un solo número natural, que no debe codificar nada.

Robin Kothari

8

@domotorp: El problema NP-completo que quería decir es, dado

, determinar si

tiene una solución

. Otra variante es, dado

, determinar si hay

tal que . (El resultado es de dx.doi.org/10.1145/800113.803627 .)

a, b, c \in N

$a,b,c\in\mathbb N$

a x^{2} + b y - c = 0

$ax^2+by-c=0$

x, y \in N

$x,y\in\mathbb N$

a, b, c

$a,b,c$

x \leq c

$x\le c$

x^{2} \equiv a (\mod b)

$x^2\equiv a\pmod b$

Emil Jeřábek apoya a Monica

3

¿Por qué la respuesta a esta pregunta no es obviamente NO ? Cada problema NP-hard tiene instancias que "codifican" un circuito booleano; posiblemente, eso es lo que significa ser NP-hard!

Jeffε

2

@domotorp: quizás otro buen candidato "natural" es el problema de encontrar las cadenas de adición mínimas de un número dado : de En el número de cadenas de adición mínimas : "... El problema de encontrar una cadena de adición mínima para un conjunto de números es NP-completo. Esto no implica, ya que a veces se afirma que encontrar una cadena de adición mínima para es NP-complete. Sin embargo, podemos deducir fácilmente que el problema de encontrar todas las cadenas de adición mínimas para un número es NP-complete ... "

n

$n$

m

$m$

n

$n$

n

$n$

Marzio De Biasi

17

Este problema tiene una variación con una sola entrada entera:

¿ $n$ un divisor estrictamente entre sus dos factores primos más grandes?

La idea es utilizar la misma reducción aleatoria de la suma del subconjunto descrita en el respuesta superior a la pregunta vinculada, pero con el rango objetivo codificado como los dos primos más grandes en lugar de proporcionarse por separado. La definición tiene un aspecto natural a pesar de que es solo una función de emparejamiento disfrazada.

Aquí hay otra variación del mismo problema, con una reducción similar del problema de partición:

Es el producto de dos enteros que difieren en menos de $n$ ? $n^{\frac{1}{4}}$

En ambas reducciones estamos "camuflando" un conjunto de enteros al encontrar números primos cercanos y tomar su producto. Si es posible hacer eso en tiempo polinómico, entonces estos problemas son NP completos.

Creo que es esclarecedor ver estos ejemplos junto con el teorema de Mahaney : si y podemos encontrar números primos cercanos, entonces estos conjuntos no son escasos. Es satisfactorio obtener una declaración puramente aritmética de la teoría de la complejidad (a pesar de que solo es conjetural y es probable que se pueda demostrar fácilmente de otra manera). $P \ne NP$

Dan Brumleve
fuente

¿Qué quieres decir con 'si P ≠ NP y podemos encontrar números primos cercanos'?

T ....

1

@ao., vea la respuesta de Peter Shor que describe la reducción. Para que sea NP-complete, necesitamos poder encontrar un primer

con

en el tiempo

. Trataré de dar mi propia cuenta de todo esto aquí más adelante.

p

$p$

| p - n | < n^{a}

$\vert p - n \vert \lt n^a$

O ((\log n)^{k})

$O((\log{n})^k)$

Dan Brumleve

¿Qué conjuntos no son densos?

T ....

33

Según la discusión, volveré a publicar esto como respuesta.

Como lo demostraron Manders y Adleman , el siguiente problema es NP-completo: dados los números naturales , determinan si existe un número natural tal que $a,b,c$ $x\le c$ $x^2\equiv a\pmod b$ .

El problema se puede enunciar de la siguiente manera: dado , determine si la cuadrática tiene una solución $b,c\in\mathbb N$ $x^2+by-c=0$ $x,y\in\mathbb N$ .

(El documento original indica el problema con , pero no es difícil ver que uno puede reducirlo al caso ). $ax^2+by-c$ $a=1$

Emil Jeřábek apoya a Monica
fuente

10

Aquí hay un $\text{NEXP}$ problema completo de con un solo número natural como entrada.

El problema consiste en colocar una cuadrícula con un conjunto fijo de mosaicos y restricciones en mosaicos adyacentes y mosaicos en el límite. Todo esto es parte de la especificación del problema; No es parte de la entrada. La entrada es solo el número . El problema es -completo para algunas opciones de reglas de mosaico como se muestra en $n \times n$ $n$ $\text{NEXP}$

D. Gottesman, S. Irani, "La complejidad cuántica y clásica de los mosaicos traduccionalmente invariantes y los problemas hamiltonianos", Proc. 50º Symp anual. sobre Fundamentos de la informática, 95-104 (2009), DOI: 10.1109 / FOCS.2009.22 . También arXiv: 0905.2419 .

El problema se define en la página 5 de la versión arxiv.

Además, también definen un problema similar que es -complete, que es el análogo cuántico de error acotado de . (El análogo clásico de error acotado de es ). $\text{QMA}_\text{EXP}$ $\text{NEXP}$ $\text{NEXP}$ $\text{MA}_\text{EXP}$

Robin Kothari
fuente

3

+1, pero es un poco difícil argumentar que el número

se está utilizando de forma "natural", ya que está codificando la entrada a una máquina de Turing particular (específicamente, el mosaico existe si la máquina de Turing acepta

, donde

es la

-ésima en una enumeración de posibles cadenas de entrada). Sigue siendo un resultado muy interesante.

n

$n$

x

$x$

x

$x$

n

$n$

mjqxxxx

Estoy totalmente de acuerdo con mjqxxxx.

domotorp

2

Creo que usando una de las variantes limitadas en el tiempo de la complejidad de Kolmogorov puede construir un problema que usa solo la representación binaria de un número y (creo) es poco probable que esté en ; informalmente es una versión decidible del problema "¿Es compresible?": $\mathsf{P}$ $n$

Problema: Dado , ¿existe una máquina Turing tal que y en una cinta en blanco producen en menos de pasos, donde es la longitud de la representación binaria de $n$ $M$ $|M| < l$ $M$ $n$ $l^2$ $l = \lceil \log{n} \rceil$ $n$

Está claramente en , porque dado y , simplemente simule para pasos y, si se detiene, compare el resultado con . $\mathsf{NP}$ $n$ $M$ $M$ $l^2$ $n$

Marzio De Biasi
fuente

Creo que este problema está bastante basado en TM pero, por supuesto, es imposible trazar una línea.

domotorp

Para refinar el comentario de domotorp, diría que el hecho de que tenga que invocar la noción de una máquina de Turing en la descripción del problema lo descarta como un "problema natural sobre los números naturales". (Si suponemos que un problema ntaural sobre números naturales es uno cuyo formato general sería coherente, por ejemplo, con Fermat habiéndolo estudiado, sin suponer una historia matemática demasiado contrafáctica.)

Niel de Beaudrap

2

$C$ $C< 220$

Igor Pak
fuente

5

$5$

10

$10$

No, 5 variables son las más pequeñas. 10 - no estoy seguro. Pero realmente no puedes tener menos de 6 ...

Igor Pak

\geq 5

$\geq5$

\geq 6

$\geq6$

\leq 4

$\leq4$

P

$P$

\leq 5

$\leq5$

\leq 5

$\leq5$

P

$P$

Sí. Para menos variables, el problema está en P.

Igor Pak

2

Sí. Todo está en nuestro trabajo y en la tesis de Danny Nguyen. math.ucla.edu/~pak/papers/Nguyen-thesis.pdf

Igor Pak

1

¿Qué tal el problema de PARTICIÓN ?

Kevin A. Wortman
fuente

3

No, ya que la entrada no es un número sino un conjunto.

domotorp

1

Entonces, ¿está pidiendo problemas para los cuales una instancia es exactamente un número natural? No creo que eso esté claro en su pregunta, ya que pide "problemas con las entradas naturales" y su ejemplo del juego Nim involucra cuatro números.

Kevin A. Wortman

Lamento si fui vago en la formulación de la pregunta.

domotorp

¿Hay un problema natural en los productos naturales que es NP-completo?

Respuestas: