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