No artigo de Stephen Cook sobre o problema P vs NP, [1] ele afirma o seguinte [2]:
Tese de Viabilidade: Um problema natural tem um algoritmo viável se tiver um algoritmo de tempo polinomial.
Minha pergunta é: o que exatamente ele (ou, em geral, realmente, o que alguém) quer dizer com "um problema natural "? Falar sobre problemas naturais parece bastante comum, mas ainda não encontrei uma definição. Parece que estou perdendo alguma coisa. Aqui estão algumas respostas possíveis em que estou pensando:
Primeira resposta possível
Cook diz em seu artigo que "natural" deve ser explicado. Ele diz: "geralmente não consideramos uma classe com um parâmetro como natural, como o conjunto de gráficos incorporáveis em uma superfície do gênero k , k > 1." [3] Agora, primeiro, isso parece dizer o que " natural "não é mais do que é; mas se todo problema é natural ou não e isso descreve completamente todos os problemas que não são naturais, isso seria suficiente para definir natural. (Mas o qualificador "em geral" sugere que essa não é uma descrição suficiente e necessária de problemas que não são naturais.)
Eu acho que "classes com parâmetros" está se referindo à rastreabilidade de parâmetros fixos, com a qual queremos dizer problemas que têm possíveis entradas restritas, de modo que a viabilidade seja forçada. Portanto, podemos resolver o problema da mochila [4] com um algoritmo de tempo polinomial se fixarmos o peso que a mochila pode suportar (mas, em geral, não há solução no tempo polinomial). Com isso em mãos, considero que "natural" significa que o problema não é restrito ("artificialmente" restrito?) De uma maneira que força um algoritmo de tempo polinomial a sair de um problema que não é solucionável no tempo polinomial.
A razão pela qual não tenho certeza de que essa é a maneira correta de entender a noção de "natural" de Cook é que não tenho certeza absoluta do que a qualificação "natural" está fazendo aqui. Se você deixar cair "natural", obterá "um problema com um algoritmo viável, se tiver um algoritmo de tempo polinomial". Mas isso parece perfeitamente razoável: o problema da mochila não possui um algoritmo viável porque não possui um algoritmo de tempo polinomial; a mochila com capacidade de rastreio de paramater fixo possui um algoritmo viável porque possui um algoritmo de tempo polinomial. Ambas as contas parecem estar de acordo com a noção de qual é o problema de um algoritmo viável.
Entendo que este pode ser o melhor guia para entender o que Cook significa, porque Cook realmente se vira e define. Também entendo que essa noção de natural é capturada por essa pergunta do StackExchange. [5}
Mas tem outro.
Segunda resposta possível
William Gasarch, em seu artigo "Classificando Problemas em Classes de Complexidade" [6], diz que conduzirá "uma discussão literal sobre o que é um problema natural" [7]. No final do artigo, [8] há uma troca em forma de diálogo, onde um palestrante diz:
"O que torna um problema natural? Por um lado, eu não construí o problema com o único objetivo de não estar em P. Portanto, não é um problema idiota. Então, ele aumenta o nível de naturalidade?"
Assim, parece-me o que Gasarch está dizendo é que, se temos um problema que não é intencionalmente construído, para que possamos dizer que não está em P, então é natural. Portanto, com um pouco de interpretação criativa, parece que Gasarch está dizendo algo pelo menos consistente com Cook: por um lado, Gasarch diz que não ser construído com o único objetivo de não estar em P torna um problema não natural; e, por outro lado, Cook diz que um problema é natural se não tiver parâmetros. Mas a mera consistência não produz uma definição.
Terceira resposta possível
Na entrada da Wikipedia para um "problema bem posicionado" [9], é apresentada uma definição da noção de Jacques Hadamard de um problema bem posicionado, e afirma-se que um problema bem posicionado "pode ser considerado um problema" natural " na medida em que existem processos físicos modelados por esses problemas ". Então, um problema é natural se, e somente se, modelar um processo físico?
As qualificações de Hadamard, de acordo com a Wikipedia, são (i) uma solução, (ii) a solução é única e (iii) o comportamento da solução muda continuamente com as condições iniciais. Isso parece ser diferente das outras duas definições. Meu senso é que "natural" não está sendo usado exatamente da mesma maneira (especialmente se concordarmos com a interpretação de que um problema é natural se e somente se ele modelar um processo físico), mas eu queria incluí-lo porque me deparei com na minha pesquisa sobre essa questão, e há pontos de contato.
Então, minha pergunta é: o que é um problema natural? Alguma dessas respostas, ou alguma combinação delas, está correta? Há alguma outra resposta que estou faltando? Obrigado.
- "The Statement of the Problem", 2006, publicado online no Clay Mathematics; title: "Problema P vs NP", http://www.claymath.org/sites/default/files/pvsnp.pdf
- p. 3
- p. 4
- https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem
- O problema natural mais conhecido em P? Entendo que um problema natural segue essa descrição, mas não restringe k a ser o maior.
- https://www.cs.umd.edu/~gasarch/papers/classcomp.pdf
- p. 2)
- p. 47-8, seção 25
- https://en.wikipedia.org/wiki/Well-posed_problem
fonte
Respostas:
Para ser claro, não é para ser formalizável. Não é um teorema, é uma observação sobre o mundo - tudo bem se "natural" for subjetivo aqui. Por analogia, se alguém diz que "diferenciação é mecânica enquanto integração é arte", não está convidando você para formalizar "mecânica" e "arte" e provar a afirmação, está tentando transmitir uma perspectiva geral. Então você pode estar sentindo falta da floresta um pouco pelas árvores aqui.
Qual é o ponto do autor
Vamos seguir sua sugestão e soltar a palavra "natural":
Portanto, o autor acha que a tese ainda é bastante precisa em relação aos problemas que realmente queremos resolver no mundo real e a outros problemas encontrados "naturalmente" no curso da vida da teoria da não complexidade. Então ele pensa, vamos chamar esses problemas de "naturais" e revisar a tese de viabilidade.
O que é e não é natural
Com certeza, um problema que geralmente surge na prática seria considerado natural: caminhos mais curtos, classificação, distância de edição, busca de raízes, vendedor ambulante, mochila.
Com certeza, um problema pensado e definido especificamente para provar um resultado de complexidade e referenciar uma classe específica não é natural. Por exemplo, "essa sequência pode ser gerada por uma máquina de Turing nos estados k em n tempo".
Algumas coisas são menos claras, como talvez programação linear, mas eu não me preocuparia muito com isso. Estude muitos algoritmos e problemas de complexidade e veja se você concorda com a ideia geral ou se encontra exemplos que você acha que a contradizem.
(De qualquer forma, acho que a rota do "problema bem colocado" está definitivamente errada a propósito, como você suspeita.)
[nota (s) de rodapé] Não pretendo desencorajá-lo a tentar formalizá-lo, apenas pensando que você deve fazê-lo.
fonte
Tudo se resume a saber se a definição do problema pode ser circular:
Um problema artificial é aquele construído para preencher seus critérios de classe.
Um problema natural não depende de seu método de construção para preencher os critérios de classe.
A construção de Ladner é conhecida por ser NP intermediária , desde que exista NPI.
fonte