Existe um problema natural no natural que é NP-completo?

30

Qualquer número natural pode ser considerado como uma sequência de bits; portanto, inserir um número natural é o mesmo que inserir uma sequência 0-1; portanto, problemas NP-completos com entradas naturais obviamente existem. Mas existem problemas naturais, ou seja, aqueles que não usam codificação e interpretação especial dos dígitos? Por exemplo "Não é primo?" é um problema tão natural, mas este está em P. Ou "Quem vence o jogo Nim com montes de tamanho 3, 5, n, n?" é outro problema que considero natural, mas também sabemos que isso é em P. Também estou interessado em outras classes de complexidade em vez de NP.

Atualização: Como apontado por Emil Jeřábek, dado para determinar se tem uma solução sobre os naturais é NP-completo. Isso é exatamente o que eu tinha em mente como natural, exceto que aqui a entrada é de três números em vez de apenas um. $a,b,c\in \mathbb N,$ $ax^2+by-c=0$

Atualização 2: e depois de mais de quatro anos de espera, Dan Brumleve deu uma solução "melhor" - observe que ela ainda não está concluída devido à redução aleatória.

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

11

Conheço um problema de lado a lado NEXP-complete, em que a entrada é um número n e o problema é determinar se existe um lado a lado válido de uma grade nxn. Se isso for interessante para você, procurarei o jornal.

226126 Robin Kothari

2

@Emil: o comentário de domotorp foi uma resposta a uma confusão que tive. Mas foi um mal-entendido da minha parte, então excluí o comentário. Eu acho que a entrada é necessária para ser um único número natural, que não deve codificar nada.

Robin Kothari

8

@domotorp: O problema NP-I completo, quer dizer é, dada

a, b, c \in N

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

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

$ax^2+by-c=0$ tem uma solução

x, y \in N

$x,y\in\mathbb N$ . Outra variante é, dado

a, b, c

$a,b,c$ , determine se existe

x \leq c

$x\le c$ tal que

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

$x^2\equiv a\pmod b$ . (O resultado é de dx.doi.org/10.1145/800113.803627 .)

Emil Jeřábek apoia Monica em

3

Por que a resposta a esta pergunta não é obviamente NÃO ? Todo problema difícil de NP possui instâncias que "codificam" um circuito booleano; indiscutivelmente, é isso que significa NP-hard!

Jeffε

2

@domotorp: talvez outro bom candidato "natural" seja o problema de encontrar as cadeias mínimas de adição de um único número : de Sobre o número de cadeias mínimas de adição : "... O problema de encontrar uma cadeia mínima de adição para um conjunto de números é NP-completo, o que não implica, pois às vezes se afirma que encontrar uma cadeia de adição mínima para é NP-completo.No entanto, podemos deduzir facilmente que o problema de encontrar todas as cadeias de adição mínimas para um número é NP-complete ... "

n

$n$

m

$m$

n

$n$

n

$n$

Marzio De Biasi

17

Esse problema tem uma variação com uma única entrada inteira:

Será que tem um divisor em estrita entre os seus dois maiores fatores primos? $n$

A idéia é usar a mesma redução aleatória da soma do subconjunto descrita na resposta superior à pergunta vinculada, mas com o intervalo de destino codificado como os dois maiores números primos em vez de dados separadamente. A definição tem uma aparência natural, mesmo que seja apenas uma função de emparelhamento disfarçada.

Aqui está outra variação do mesmo problema, com uma redução semelhante do problema de partição:

é o produto de dois números inteiros que diferem em menos de ? $n$ $n^{\frac{1}{4}}$

Em ambas as reduções, estamos "camuflando" um conjunto de números inteiros localizando números primos próximos e obtendo seu produto. Se for possível fazer isso em tempo polinomial, esses problemas serão NP-completos.

Eu acho que é esclarecedor olhar para esses exemplos, juntamente com o teorema de Mahaney : se e podemos encontrar números primos próximos, esses conjuntos não são escassos. É gratificante obter uma afirmação puramente aritmética da teoria da complexidade (mesmo que seja apenas conjetural e provavelmente provável de outra maneira). $P \ne NP$

Dan Brumleve
fonte

o que você quer dizer com 'se P ≠ NP e podemos encontrar números primos próximos'?

T ....

11

@ao., veja a resposta de Peter Shor descrevendo a redução. Para ser NP-completo, precisamos encontrar um primo com no tempo . Tentarei dar conta de tudo isso aqui mais tarde.

p

$p$

| p - n | < n^{a}

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

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

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

Dan Brumleve

Quais conjuntos não são densos?

T ....

33

Com base na discussão, vou repassar isso como resposta.

Como provado por Manders e Adleman , o seguinte problema é NP-completo: dados os números naturais , determinam se existe um número natural tal que $a,b,c$ $x\le c$ . $x^2\equiv a\pmod b$

O problema pode ser equivalentemente indicou o seguinte: dada , determinar se o quadrática tem uma solução . $b,c\in\mathbb N$ $x^2+by-c=0$ $x,y\in\mathbb N$

(O artigo original declara o problema com , mas não é difícil ver que é possível reduzi-lo ao caso ) $ax^2+by-c$ $a=1$

Emil Jeřábek apoia Monica
fonte

10

Aqui está um problema completo da com um único número natural como entrada. $\text{NEXP}$

O problema é de cerca de ladrilhos um grade com um conjunto fixo de telhas e restrições em telhas adjacentes e azulejos na fronteira. Tudo isso faz parte da especificação do problema; não faz parte da entrada. A entrada é apenas o número . O problema é completo para algumas opções de regras de mosaico, conforme mostrado em $n \times n$ $n$ $\text{NEXP}$

D. Gottesman, S. Irani, "A Complexidade Quântica e Clássica de Azulejos Translacionalmente Invariáveis e Problemas Hamiltonianos", Proc. 50º Symp anual. em Fundamentos de Ciência da Computação, 95-104 (2009), DOI: 10.1109 / FOCS.2009.22 . Também arXiv: 0905.2419 .

O problema está definido na página 5 da versão do arxiv.

Além disso, eles também definem um problema semelhante que é complete, que é o análogo quântico de erro limitado do . (O analógico clássico de erro limitado do é .) $\text{QMA}_\text{EXP}$ $\text{NEXP}$ $\text{NEXP}$ $\text{MA}_\text{EXP}$

Robin Kothari
fonte

3

+1, mas é um pouco difícil argumentar que o número

está sendo usado de maneira "natural", pois codifica a entrada para uma determinada máquina de Turing (especificamente, a telha existe se a máquina de Turing aceitar

, em que

é o

ésimo em uma enumeração de possíveis cadeias de entrada). Ainda é um resultado muito interessante.

n

$n$

x

$x$

x

$x$

n

$n$

Mjqxxxx 30/10/12

Eu concordo maximamente com mjqxxxx.

Domotorp 31/10/12

2

Eu acho que usando uma das variantes de complexidade de Kolmogorov, com limite de tempo, você pode criar um problema que usa apenas a representação binária de um número e (eu acho) é improvável que esteja em ; informalmente, é uma versão decidível do problema "Is compressible?": $\mathsf{P}$ $n$

Problema: Dado , existe uma máquina de Turing modo que e em saídas de uma fita em branco em menos do que passos, onde é o comprimento da representação binária de $n$ $M$ $|M| < l$ $M$ $n$ $l^2$ $l = \lceil \log{n} \rceil$ $n$

É claramente em , porque dado e , apenas simular para etapas e se ele pára comparar o resultado com o . $\mathsf{NP}$ $n$ $M$ $M$ $l^2$ $n$

Marzio De Biasi
fonte

Eu acho que esse problema é bastante baseado na TM, mas é claro que é impossível traçar uma linha.

Domotorp 31/10/12

Para refinar o comentário de domotorp, eu diria que o fato de ter que invocar a noção de uma máquina de Turing na descrição do problema a exclui como um "problema natural sobre números naturais". (Se supusermos que um problema ntaural sobre números naturais é aquele cujo formato geral seria consistente por exemplo, com Fermat ter estudado ele, sem supor também contrafactual a história da matemática.)

Niel de Beaudrap

2

Nosso artigo do FOCS'17 sobre Aritmética de Presburger Curto é um exemplo de um problema "natural" que é o NP-c e usa um número constante $C$ de números inteiros na entrada, digamos $C< 220$ . É diferente de Manders-Adleman, pois as restrições são todas desigualdades. Veja o post de Gil Kalai no blog para obter mais informações.

Igor Pak
fonte

Eu acho que isso é mais natural que Manders-Adleman. É menor que

variáveis e

exemplos de desigualdade são possíveis?

5

$5$

10

$10$

T ....

Não, 5 variáveis é a menor. 10 - não tenho certeza. Mas você realmente não pode ter menos de 6 ...

Igor Pak

Existe uma razão por trás de

e

? Quero dizer, está provado que todos

e número finito de desigualdades estão em

(da mesma forma que todas as

variáveis e

formulações de desigualdades estão em

?)?

\geq 5

$\geq5$

\geq 6

$\geq6$

\leq 4

$\leq4$

P

$P$

\leq 5

$\leq5$

\leq 5

$\leq5$

P

$P$

T ....

Sim. Para menos variáveis, o problema está em P.

Igor Pak

2

Sim. Está tudo em nosso artigo e na tese de Danny Nguyen. math.ucla.edu/~pak/papers/Nguyen-thesis.pdf

Igor Pak

1

E o problema da PARTIÇÃO ?

Kevin A. Wortman
fonte

3

Não, pois a entrada não é um número, mas um conjunto.

Domotorp 31/10/12

11

Então, você está solicitando problemas para os quais uma instância é exatamente um número natural? Não acho isso claro na sua pergunta, pois você pede "problemas com insumos naturais" e seu exemplo do jogo Nim envolve quatro números.

Kevin A. Wortman

Lamento se fui vago na formulação da pergunta.

Domotorp 31/10/12

Existe um problema natural no natural que é NP-completo?

Respostas: