Função que é garantida como unidirecional se existirem funções unidirecionais?

13

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?

Timothy Chow
fonte
Oi Timothy Chow, talvez você possa ajudar e apontar para um link onde o truque para escrever um algoritmo, que se P = NP, resolve SAT em tempo polinomial, é formalizado? Obrigado allot
Avi Tal
@AviTal Veja, por exemplo, o seguinte: scholarpedia.org/article/Universal_search
Vanessa

Respostas:

11

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.

Bjørn Kjos-Hanssen
fonte
Obrigado! Usando o Google Scholar, eu pude usar essa referência para encontrar uma referência para um sistema de criptografia de chave pública completo, de Grigoriev, Hirsch e Pervyshev, Groups-Complexity-Cryptology 1 (2009), 1-12.
Timothy Chow
Você poderia explicar detalhes dessa função? Por que ele é interrompido após n ^ 2 etapas, por que "preservar uma cópia do prefixo do programa e forçá-lo, assim como o comprimento da entrada, na saída" e o que "apenas em locais onde essa extensão possível é única" significa exatamente . Não sei se isso merece uma pergunta separada.
galmeida 6/09/19
@ BjørnKjos-Hanssen cstheory.stackexchange.com/questions/44496/…
galmeida