Existem problemas conhecidos de PN que são conjecturados como sendo exponencialmente difíceis em média?

11

A ETH afirma que o SAT não pode ser resolvido no pior dos casos no tempo subexponencial. E o caso médio? Existem problemas naturais em PN que são conjecturados como sendo exponencialmente difíceis no caso médio?

Tome caso médio para significar o tempo médio de execução com distribuição uniforme nas entradas.

cc.complexity-theory np average-case-complexity Anônimo
fonte
6
você precisa de uma definição para "caso médio" para tornar sua pergunta matematicamente significativa.
Yixin Cao
2
vzn, eu não entendo a relevância do seu comentário. Não estou perguntando sobre um problema em aberto aqui, é óbvio que não há problemas que se sabe serem difíceis em média. Estou perguntando se existem candidatos que são conjecturados para serem difíceis, em média. Por favor, leia a pergunta cuidadosamente antes de comentar.
Anónimo
1
@vzn Exatamente! Eu definitivamente concordo, meu significado é que parece difícil para uma dessas conjecturas dar um passo significativo adiante ou mudar substancialmente as direções da pesquisa que você mencionou.
usul
3
OP, observe que o tempo de execução esperado não é AFAIK a quantidade usual que observamos na dureza média dos casos. ver alguns pesquisa sobre a teoria média complexidade caso de Levin
Sasho Nikolov
1
Sasho Nikolov, estou ciente da teoria de Levin. No entanto, há também uma complexidade média de caso mais simples usada para analisar o comportamento de algoritmos em uma distribuição específica que remonta a [Karp 1986], que é mais comum em algoritmos. Estou ciente de que o problema do lado a lado e alguns outros problemas estão completos para o DistNP. No entanto, não sei se elas são conjecturadas como exponencialmente difíceis, em média, usando o significado simples de caso médio devido a Karp.
Anônimo

Respostas:

11

Pode-se supor que a Paridade de Aprendizagem com Problema de Ruído (LPN) a uma taxa de erro constante requer tempo . O algoritmo mais rápido conhecido (Blum-Kalai-Wasserman) usa o tempo 2 O ( n / log n ) .2n1−o(1)2O(n/log⁡n)

Ryan O'Donnell
fonte
Obrigado. Poderia, por favor, fornecer referências onde posso ler mais sobre o problema do LPN?
Anónimo
2
@Anônimo: Este artigo apresenta várias conjecturas sobre a dureza do LPN: M. Alekhnovich. “Mais em caso médio versus complexidade de aproximação.” Em Proc. do 44º Simpósio de Fundamentos da Ciência da Computação, pp. 298-307, 2003.
Yury
Yury, obrigado pela referência: math.ias.edu/~misha/papers/average.ps
Anônimo
10

ncnc

David Eppstein
fonte
Obrigado. Existe uma razão para eles não conjeturarem a afirmação mais forte de que a taxa aleatória de k-SAT restrita à cláusula próxima ao limite de satisfação é exponencialmente difícil?
Anônimo
4
Meu palpite é que é porque eles podem provar resultados sobre algoritmos de backtracking que não são condicionais em P ≠ NP.
David Eppstein
5

Existem vários geradores de números aleatórios que não temos algoritmos de tempo polinomial para quebrar. Eu acho que você pode considerá-los difíceis em casos médios. Confira os geradores em www.ecrypt.eu.org/stream/ Existem outros, é claro, você pode pesquisar a maioria deles online.

William Hird
fonte
Existe algum PRNG polytime em particular que é conjecturado como exponencialmente difícil em média?
Anónimo
O gerador de passo alternado inventado por Gunther é uma beleza por várias razões. São necessários dois registros de deslocamento de realimentação linear (LFSR) A & B e XOR como saída, mas o relógio dos dois registradores é controlado por um terceiro LFSR (C), de modo que as saídas de A e B entrem no portão XOR de maneira irregular. Como os bits de C controlam apenas o clock de A e B e não aparecem no fluxo de saída, C pode ser considerada uma variável quase oculta que rompe a linearidade inerente de A e B. Essa é uma explicação simplificada, mas você desejará para ver o circuito por si mesmo.
precisa
Não estou familiarizado com "Alternating Step Generator inventado por Gunther". É conjecturado que seja exponencialmente difícil em média?
Anónimo
1
Não sei como responder ao seu comentário, mas o ASG é considerado inquebrável, desde que os comprimentos das chaves dos três registros de turno sejam de 128 bits cada. Se isso equivale a ser "exponencialmente difícil em média", acho que sua resposta é sim.
precisa
1
@Anonymous: É claro que o ASG "básico" pode ser mais difícil de quebrar usando três ASGs como registros AB&C para outro ASG, Gunther faz alusão a isso em seu artigo original. É como adicionar mais rodadas a uma cifra de bloco. Quão longe se pode amplificar dureza por este método é uma questão em aberto (e interessante) :-)
William Hird
-1

meu entendimento é que, embora existam alguns candidatos da teoria da inquebrabilidade da criptografia e geradores de números aleatórios [por exemplo, alguns citados em Razborov / Rudich, Natural Proofs], a maioria dos aspectos de sua pergunta é reconhecida como basicamente questões-chave "ainda abertas" por especialistas no campo. desde a introdução à pesquisa abrangente, Complexidade Média de Casos de Bogdanov e Trevisan (2006) apresenta alguns pontos relacionados. A palestra do Trevisan no youtube sobre descobertas e perguntas abertas de complexidade média de casos também pode ser útil.



≠

≠

As técnicas corretas para aplicar essa teoria a problemas e distribuições naturais ainda não foram descobertas. Desse ponto de vista, o estado atual da teoria da complexidade de casos médios em PN é semelhante ao estado da teoria de inadequação de problemas de otimização de PN antes do teorema do PCP.

vzn
fonte
2
Não é uma resposta para minha pergunta. Pensei ter explicado a você que não estou procurando comentários gerais sobre assuntos relacionados, mas sim problemas candidatos que sejam conjecturados como difíceis .
Anónimo
1
tanto faz! imho "a teoria não tem uma resposta substancial para sua pergunta neste momento", juntamente com algumas das melhores / mais úteis referências / autoridades disponíveis sobre o assunto, é uma resposta legítima à sua pergunta, que foi postada não apenas para você
vzn 5/12/12
1
@ Anonymous, ainda estou um pouco confuso sobre o seu significado de "conjecturado". Todos nós podemos ter nossas conjecturas pessoais, por isso não está claro se você está procurando uma opinião pessoal, uma posição em relação a uma pergunta aberta que é compartilhada por muitas pessoas na pesquisa ou algo assim. Pode ser útil fornecer uma declaração mais precisa do que você está procurando. Além disso, acho que respostas como a vzn são instrutivas e informativas, mesmo que não estejam diretamente relacionadas à sua pergunta exata; portanto, não vejo que essas respostas devam ser tão fortemente desencorajadas.
Usd
2
Se você leu meu comentário ao qual Peter Shor respondeu, já estou ciente dos problemas criptográficos que são conjecturados como sendo superpolinomialmente difíceis. Por favor, leia a pergunta com atenção, não estou procurando problemas superpolinomialmente difíceis, estou procurando problemas exponencialmente difíceis.
Anónimo
2
Por favor, leve mais discussão para conversar.
Jeffε 5/12