Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/a^b eq c mod d in P — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) м (StasFomin переименовал страницу Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/принадлежит ли P в [[Полиномиальные сводимости …) |
StasFomin (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
− | |||
<latex> | <latex> | ||
1. Покажите, что язык L_{ind}=\backslash\{a,b,c,d\, \text{натуральные числа такие, что},$a^b$=c\, mod\, d\,\}\, \text{принадлежит}\,P | 1. Покажите, что язык L_{ind}=\backslash\{a,b,c,d\, \text{натуральные числа такие, что},$a^b$=c\, mod\, d\,\}\, \text{принадлежит}\,P | ||
Строка 6: | Строка 5: | ||
2. Укажите два слова, принадлежащие языку, и два слова, не принадлежащие языку. | 2. Укажите два слова, принадлежащие языку, и два слова, не принадлежащие языку. | ||
</latex> | </latex> | ||
+ | |||
+ | [[Category:Решенные задачи]] |
Версия 11:13, 20 мая 2015