No filme Inception, Cobb pede a Ariadne para projetar um labirinto que leva o dobro do tempo para projetar. Isso se presta a um problema generalizado em que temos uma situação em que temos recursos limitados em alguma quantia e quem verificará se esse problema está na classe de complexidade fornecida que levará mais tempo e / ou espaço para resolver. Isso é um problema novo?
Respostas:
Essa situação surge com freqüência em criptografia, na qual você deseja gerar instâncias de problemas difíceis junto com suas soluções. Por exemplo, há o trabalho de Eric Bach (e mais tarde, Adam Kalai) na geração eficiente de números inteiros aleatórios com suas fatorações primárias.
Uma das muitas observações interessantes de Impagliazzo e Wigderson (Randomness vs time: derandomization sob uma suposição uniforme. J. Comput. Syst. Sci., 63: 672–688, 2001) é que se pode gerar eficientemente matrizes aleatórias uniformes módulo p junto com suas permanentes. (Pense nisso ... use a auto-redutibilidade da permanente ....) Além disso, sabemos que a permanente é auto-redutível aleatoriamente . Portanto, este é um exemplo de um problema muito difícil para o qual podemos gerar instâncias resolvidas com eficiência.
fonte
Primeiro, não acho que o protocolo Arthur-Merlin tenha que entrar no modelo - parece que a motivação é que você deseja produzir instâncias de problemas rapidamente, para que qualquer algoritmo para resolvê-las seja lento. Em outras palavras, se pudéssemos provar que Arthur pode produzir um problema difícil, parece não haver necessidade de Merlin verificar se o problema produzido é difícil.
Muito relacionada é esta pergunta : podemos gerar no tempo polinomial uma linguagem que não é decidível no tempo polinomial? A resposta acaba sendo sim se P unário não for igual a NP unário.
fonte