O que está faltando para esta prova p! = Np?

Question

Eu tentei recuperar uma senha. Ao pensar nisso, reconheci que o problema "recuperação de senha" é um exemplo muito bom de um problema de NP. Se você souber a senha, é muito fácil verificá -la no tempo polinomial. Mas se você não souber a senha, precisa pesquisar todo o espaço de possíveis soluções que podem ser mostradas para levar tempo exponencial.

Agora, minha pergunta é: isso não demonstra que P! = NP, já que a "recuperação de senha" é um elemento de NP que pode ser mostrado para exigir mais do que o tempo polinomial para executar?

Answer 1

O problema não está mostrando que a recuperação de senha não é polinomial, pois claramente é-você precisa pesquisar um espaço exponencial de respostas.

Na verdade, "recuperação de senha" não é realmente uma descrição de um padrão Problema computacional. Parece que, formalmente, os algoritmos de quebra de senha levam algum tipo de "oracle" que pode responder se uma determinada string é a senha correta. No entanto, P e NP são definidos em termos de máquinas de Turing, que tomam cordas como entrada.

Answer 2

Se você mostrar isso algum O algoritmo que resolve a "recuperação de senha" requer mais do que o tempo polinomial, então demonstra que P ≠ NP.

Caso contrário, se você só mostrar isso uma solução específica requer mais do que tempo polinomial, não demonstra nada. Posso escrever um tipo para exigir tempo exponencial (matriz de embaralhamento até que seja classificada), mas isso não significa que não haja solução polinomial.

Answer 3

O NP não significa "não polinomial", se é isso que você estava pensando (e minhas desculpas antecipadamente se não fosse!). Significa "polinomial não determinístico". Um algoritmo não determinístico é equivalente a um número ilimitado de instâncias paralelas de um algoritmo. Como exemplo, encontrar a senha correta por força bruta é polinômio não determinístico: se você imagina que verificando a senha, se o seu palpite estiver correto, leva o tempo linear (ou seja, polinomial) na duração da senha, mas que você precisa Verifique um número arbitrário de senhas possíveis (k^n) em paralelo; o custo de encontrar a solução usando esse método é polinomial não determinístico.

Um algoritmo não -determinístico também pode ser pensado em alguém cujos ramos do estado em alguns passos. Um exemplo simples disso é um autômato finito não determinístico (NFA) - às vezes você não sabe qual vantagem ter entre estados, então você leva os dois. É fácil mostrar que todo NFA é equivalente a uma FA determinística e, portanto, é tentador pensar que o mesmo pode ser comprovado para outras classes interessantes de algoritmo. Infelizmente, é difícil fazê -lo para o caso geral de algoritmo polinomial, e a suspeita geral é que eles não são equivalentes, ou seja, que p! = Np.

Answer 4

O raciocínio de que o problema está no NP está correto: se pode ser verificado no tempo polinomial, está no NP. Mesmo problemas muito simples estão no NP. Basicamente, todo P está incluído no NP. (*)

Agora, aqui está uma maneira de você poder transformar isso em uma prova de que p! = Np:

1) Mostre que a "recuperação de senha" é NP-complete. Ou seja, qualquer problema no NP pode ser reduzido para "recuperação de senha" no tempo polinomial. (ou seja, existe um algoritmo eficiente para converter qualquer outro problema de NP em "recuperação de senha".)

2) Depois de ter isso, como Pavel Shved menciona, não é suficiente mostrar que o algoritmo intuitivo é não polinomial. Você deve mostrar que não existe um algoritmo polinomial para resolver "recuperação de senha". Uma tarefa muito difícil.

(*) Edmund também está certo: NP significa polinômio em uma máquina não determinística. Uma verificação polinomial é essencialmente o caminho escolhido pela máquina não determinística.

Answer 5

1. Como afirmado, "recuperação de senha" não é um problema de decisão.
2. Você não provou que a "recuperação de senha" não possui um algoritmo de tempo polinomial, você apenas argumentou por motivos intuitivos que não. Só porque um espaço de solução é gigantesco não significa que não há algoritmos rápidos para encontrar a solução; por exemplo, existem n! permutações de um conjunto de n números inteiros distintos, mas apenas um é classificado ascendente, mas podemos encontrá -lo em n log n Tempo. Para um exemplo mais divertido, veja Projeto Euler #67.
3. Mesmo se você reformular a "recuperação de senha" como um problema de decisão e foi capaz de mostrar que não existe um algoritmo de tempo polinomial para resolvê-lo, agora você deve provar que a "recuperação de senha" é completa.

Para detalhes sobre p/np/etc. Veja isso pergunta anterior.

Answer 6

A declaração formal desse problema seria aquela que aceita como entrada o valor de hash (e sal) e tentativas de encontrar uma Senha que gerará esse hash: seu problema básico de colisão do CypherText básico.

Dependendo da qualidade do hash, este pode não requer tempo exponencial. De fato, muitos hash criptográficos em uso generalizado identificaram ataques que correm mais rápido que as pesquisas de chaves.

Ou seja: você (e alguns dos outros respondedores) têm assumido Que a rotina de munição de senha tem todas as propriedades que os designers queriam que eles tivessem. Isso teria que ser provou.

Answer 7

Escrever essa resposta porque tive essa ideia em algum momento, e as respostas aqui não foram satisfatórias.

Você provou que p =/= np sob a presença de um 'oracle' (isso é o que diz se a senha está certa ou não).

Foi demonstrado que você não pode provar o P vs NP original usando Oracles (essa técnica é chamada de relativização).

Para provar o problema original, você deve definir o Oracle em termos de uma máquina de Turing. Em outras palavras, você deve descrever o que o verificador de senha faz com a entrada e, em seguida, provar que não há algoritmo que possa adivinhar a senha, dado o código do verificador de senha.

Observe que você precisa fazer isso para qualquer possível verificador de senha rápida. O único requisito do algoritmo de verificador de senha é que ele é executado no tempo polinomial em relação ao comprimento da senha.

Portanto, dado qualquer algoritmo possível que verifique se a senha está certa ou não no tempo polinomial, você deve escrever um algoritmo que lê o algoritmo do verificador e tenta adivinhar que a senha está em tempo polinomial. Se você pode provar ou refutar que existe esse algoritmo, resolveu o problema.