Лемма о невозможности существования вычислительно безопасных шифров в случае P = NP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулировка)
(Формулировка)
Строка 1: Строка 1:
 
==Формулировка==
 
==Формулировка==
  
Пусть '''P''' <tex>=</tex> '''NP'''. Имеется набор схем шифрования <tex>\{E_{i}, D_{i}\}</tex>, где <tex>0 \le i \le k = 2^{n}</tex>, <tex>E_{i} \in P</tex>, <tex>D_{i} \in P</tex>. На схему подаются слова длина <tex>m</tex>, при этом <tex>m \gr n</tex>.
+
Пусть '''P''' <tex>=</tex> '''NP'''. Имеется набор схем шифрования <tex>\{E_{i}, D_{i}\}</tex>, где <tex>0 \le i \le k = 2^{n}</tex>, <tex>E_{i} \in P</tex>, <tex>D_{i} \in P</tex>. На схему подаются слова длина <tex>m</tex>, при этом <tex>m \g n</tex>.

Версия 13:03, 26 мая 2010

Формулировка

Пусть P [math]=[/math] NP. Имеется набор схем шифрования [math]\{E_{i}, D_{i}\}[/math], где [math]0 \le i \le k = 2^{n}[/math], [math]E_{i} \in P[/math], [math]D_{i} \in P[/math]. На схему подаются слова длина [math]m[/math], при этом [math]m \g n[/math].