Главная
Проблема исчисления предикатов
Процедура унификации
Отношения на функциях принадлежности
Неразрешимые алгоритмические проблемы МТ
Полнота и непротиворечивость
NP-полные (универсальные) задачи
Стандартизация услуг
Стандартизация и экология
Организационные и методические принципы сертификации в России
Программа сертификации
Метрологический надзор
Структура кристаллов
Судьбы крестьянские
Еще одна фальшивая ценность
Такая судьба
Соприкосновение с рынком
Мой театр, мои коллеги
Гастроли
И жизнь и слезы и любовь
Возвращение из Томска
Реклама:
|
|
NP-полные (универсальные) задачи
акой конфигурацией дает ответ такой же как задача П1.
Этот факт обозначают так П1µП2.
В теории сложности доказывается утверждение о том, что, если П1µП2 и П2?P, то П1?P.
Доказательство. МТ для задачи П1 есть суперпозиция МТ, обеспечивающей кодировку П1 в термины П2, и МТ решения П2. Время решения П1 Т1(n)=Tµ(n)+T2(n). Где Tµ(n)Аналогично доказывается утверждение: если П1µП2 и П2?NP, то П1?NP.
NP–полные задачи. Массовая задача П2 называется NP-полной, если П2?NP и любая задача П1?NP сводится к П2 полиномиально: П1µП2. Класс всех NP-полных задач обозначается NPC (NP-сomplete). На
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
