Лемма о невозможности существования вычислительно безопасных шифров в случае 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 > n</tex>. | + | Пусть '''P''' <tex>=</tex> '''NP'''. Имеется набор схем шифрования <tex>\{\langle E_{i}, D_{i}\rangle\}</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 > n</tex>. |
Версия 13:05, 26 мая 2010
Формулировка
Пусть P NP. Имеется набор схем шифрования , где , , . На схему подаются слова длина , при этом .
