Existe um velho truque para escrever um algoritmo que, se P = NP, resolve SAT em tempo polinomial. Essencialmente, listamos todas as máquinas do tempo polinomiais e várias tarefas sobre elas.
Existe um truque análogo para funções de mão única (ou mesmo funções de alçapão de mão única)? Ou seja, podemos escrever uma função que, se existirem funções unidirecionais, é necessariamente uma função unidirecional?
Parece não haver uma maneira fácil de imitar o truque P = NP. Nesse caso, podemos reconhecer rapidamente uma solução quando obtemos uma. Mas se eu executar várias tarefas em todas as funções de tempo polinomial, não há maneira óbvia de reconhecer uma função unidirecional quando eu chegar a uma.
Se a resposta para a pergunta acima for negativa, existe algum tipo de argumento para que não possamos fazê-lo? Talvez a anotação dessa função provasse de alguma forma que as funções unidirecionais existem?
fonte
Respostas:
Sim, essa função foi encontrada pelo próprio Levin, publicado recentemente:
A história das funções de mão única . Problemas de transmissão de informações (= Problemy Peredachi Informatsii), 39 (1): 92-103, 2003.
fonte