Qual seria a = NP prova P ser como, hipoteticamente?
https://stackoverflow.com/questions/900273
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Seria um algoritmo polinomial tempo para um determinado problema NP-completo, ou apenas raciocínios abstratos que demonstram soluções para problemas NP-completos existe?
Parece que o algoithm um específico é muito mais útil. Com isso, todos nós vamos ter que fazer para resolver polinomialmente um problema NP é para convertê-lo em um problema NP-completo específico para o qual a prova tem uma solução, e estamos a fazer.
Solução
P = NP: "A 3SAT problema é um problema completa clássico NP Nesta prova. , demonstramos um algoritmo para resolvê-lo que tem um assintótica ligados de (n ^ 99 log log n). primeiro nós ... "
P = NP: "Suponha que havia um algoritmo polinomial para o 3SAT problema Este. implicaria que .... que por ..... implica que podemos fazer .... e então ... e então ... o que é impossível. Isso tudo foi baseada em um algoritmo de tempo polinomial para 3SAT. Assim P ! = NP. "
Atualizar : Talvez algo como este papel (para P! = NP).
UPDATE 2 : Aqui está um vídeo de Michael Sipser esboçando uma prova para P! = NP
Outras dicas
Chame-me pessimista, mas ele vai ser assim:
...
?, P ? NP
QED
Existem algumas meta-resultados sobre o que um P = NP ou P ? NP prova pode não se parecem. Os detalhes são bastante técnico, mas sabe-se que a prova não pode ser
-
relativização , que tipo de meios que a prova deve fazer uso da definição exata da máquina de Turing utilizado, porque com algumas modificações ( "oráculos", como instruções CISC muito poderosas adicionadas ao conjunto de instruções) P = NP, e com algumas outras modificações, P ? NP. Veja também este post para uma boa explicação de relativização.
-
naturais , uma propriedade de vários clássico provas,
-
ou algebrizing , uma generalização relativizando.
Pode tomar a forma de demonstrar que assumindo ligações P ? NP para uma contradição.
Pode não ser ligado a P e NP de uma forma direta ... Muitos teoremas agora são baseados em P! = NP, então provar um fato assumido como falso faria uma grande diferença. Mesmo provando algo como aproximação relação constante por TS deve ser suficiente IIRC. Eu acho que, existência de NPI (GI) e outros conjuntos também é baseado em P! = NP, então fazer qualquer um deles igual a P ou NP pode mudar completamente a situação.
IMHO tudo acontece agora em um nível muito abstrato. Se alguém prove nada sobre P = /! = NP, ele não tem de mencionar qualquer um desses conjuntos ou até mesmo um problema específico.
Provavelmente seria na forma de uma redução de um problema NP para um problema P. Veja a página da Wikipedia sobre reduções .
ou
Set N igual à identidade multiplicativo. Então NP = P. QED. ; -)
A maneira mais simples é para provar que não é uma solução em tempo polinomial para os problemas da classe NP-completos. Estes são problemas que estão em NP e são reducable para um dos problemas np conhecida. Isso significa que você poderia dar um algoritmo mais rápido para provar a problema original colocada por Stephen cozinheiro ou muitos outros que também foram mostrados para ser NP-completo. papel seminal See de Richard Karp e este livro para problemas mais interessantes. Tem sido demonstrado que, se você resolver um destes problemas de toda a classe de complexidade entra em colapso. edit: eu tenho que acrescentar que eu estava conversando com meu amigo que está estudando computação quântica. Embora eu não tinha idéia do que isso significa, ele disse que uma determinada prova / experiência? no mundo quântico poderia fazer toda a classe de complexidade, eu quero dizer a coisa toda, discutível. Se alguém aqui sabe mais sobre isso, por favor responda.
Também houve numerosas tentativas para o problema sem dar um algoritmo formal. Você poderia tentar contar o set. Theres A prova Robert / Seymore. As pessoas também têm tentado resolvê-lo usando a prova diagonlization experimentado e testado (também usado para mostrar que há problemas que você nunca pode resolver). Razborov também mostrou que, se há certas funções de sentido único, então qualquer prova não pode dar uma resolução. Isso significa que novas técnicas serão necessárias a fim de resolver esta questão.
Sua sido 38 anos desde que o artigo original foi publicado e ainda não há sinal de uma prova. Não só isso, mas muitos dos problemas que os matemáticos tinham sido posando antes da noção de classes de complexidade veio em foi mostrado ser NP. Os mesmos muitos matemáticos e cientistas da computação acreditam que alguns dos problemas são tão fundamentais que um novo tipo de matemática pode ser necessária para resolver o problema. Você tem que manter em mente que a melhor corrida mente humana tem a oferecer têm abordado este problema sem qualquer sucesso. Eu acho que deveria ser, pelo menos, décadas antes rachaduras alguém o quebra-cabeça. Mas mesmo se não houver uma solução em tempo polinomial as constantes ou o expoente pode ser tão grande que seria inútil em nossos problemas.
Há um excelente levantamento disponível, que deve responder a maioria das suas perguntas: http: // www .scottaaronson.com / papers / pnp.pdf .
Certamente uma prova descritiva é o mais útil, mas há outras categorias de prova: é possível, por exemplo, para fornecer 'provas existência' que demonstram que é possível para encontrar uma resposta sem encontrar (ou, às vezes, até mesmo sugerindo como encontrar) a resposta.
É provavelmente olhar quase exatamente como uma das estes
Boa pergunta; que poderia levar qualquer forma. Obviamente, o algoritmo específico seria mais útil, sim, mas não há nenhuma determinação de que essa seria a maneira que um P teórica = NP prova iria ocorrer. Tendo em conta que a natureza dos problemas NP-completos e quão comum são, parece que mais esforço tem sido colocado em resolver esses problemas do que tem sido posta em resolver o lado teórico raciocínio da equação, mas isso é apenas suposição.
Qualquer prova não-construtiva que P = NP realmente não é. Isso implicaria que os seguintes explícitas 3-SAT algoritmo roda em tempo polinomial:
Enumerar todos os programas. Na rodada i , executar todos os programas numerados menos de i para uma etapa. E se um programa termina com um satisfazendo entrada para a fórmula , o retorno true . Se um programa termina com um prova formal de que nenhuma entrada existe , o retorno false .
Se P = NP, então existe um programa que é executado no tempo O (poli (N)) e emite uma entrada que satisfaça à fórmula, se uma tal fórmula existe.
Se P = coNP, existe um programa que é executado no tempo O (poli (N)) e emite uma prova formal de que não existe fórmula, se não existe fórmula.
Se P = NP, em seguida, uma vez que P é fechada sob complemento NP = coNP. Assim, existe um programa que é executado no tempo O (poli (N)) e faz as duas coisas. Esse programa é o k 'th programa na enumeração. k é O (1) ! Uma vez que é executado em O (poli (N)) nossa força de simulação bruta requer apenas
K * O (poli (N)) + O (poli (N)) ^ 2
rodadas uma vez que atinge o programa em questão. Como tal, a força bruta simulações em tempo polinomial!
(Note que k é exponencial no tamanho do programa; esta abordagem não é realmente viável, mas sugere que seria difícil de fazer uma prova não-construtiva que P = NP, mesmo que fosse o caso.)
Em certa medida, a formar um necessidades Essa prova ter depende do seu ponto de vista filosófico (= os axiomas que você considera para ser verdade) - por exemplo, como um construtivista você exigiria a construção de um algoritmo real que requer tempo polinomial para resolver um problema NP-completo. Isso poderia ser feito por meio de redução, mas não com uma prova indireta. De qualquer forma, ele realmente parece ser muito improvável:)
A prova seria deduzir uma contradição a partir do pressuposto de que, pelo menos, um elemento (problema) de NP não é também um elemento de P.
