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