Muitos resultados em criptografia dependem de resultados / conjecturas de impossibilidade na teoria da complexidade. Por exemplo, acredita-se que a criptografia de chave pública usando RSA é possível devido à conjectura sobre a inviabilidade do fatoramento (e os problemas de localização modular da raiz).
Minha pergunta é :
temos resultados semelhantes na teoria da computabilidade? Existem construções positivas interessantes usando resultados de impossibilidade negativos?
Por exemplo, a indecidibilidade do problema de parada nos permite executar tarefas que não poderíamos realizar se o problema de parada fosse decidível?
Respostas:
Em certo sentido, é disso que trata a teoria da parametridade.
A abstração de dados é como garantimos que nenhum cliente de um módulo possa acessar os elementos de um módulo, exceto de acordo com a interface exposta pelo módulo. Contamos com isso para garantir que os invariantes internos das estruturas de dados não possam ser quebrados pelos clientes de um módulo - por exemplo, se você acessar uma árvore balanceada apenas pela interface publicada, segue-se que a árvore sempre será balanceada.
Portanto, usamos uma propriedade negativa - que nenhum cliente possível pode quebrar o limite de abstração - para deduzir um positivo - que a invariante de representação de dados sempre mantém.
fonte
A complexidade de Kolmogorov pode se enquadrar nessa categoria.
Pode-se mostrar que existem certas cordas que não podem ser comprimidas por nenhuma máquina de Turing. Essas cadeias se comportam "genericamente" para que você possa estudar as propriedades aleatórias de determinadas informações e tarefas computacionais, estudando o comportamento em relação a uma cadeia incompressível (não aleatória).
fonte