|
 |
Персональные инструменты
Просмотры |
|
Персональные инструменты |
|
||
|
|
NP — различия между версиямиМатериал из CustisWiki
Версия 07:40, 7 декабря 2005Класс задач, разрешимых на недетерминированной машине Тьюринга за полиномиальное время, т.е, через определение класса NTIME:
Можно показать также эквивалентное определение через детерминированную машину Тьюринга. Определение через детерминированную машину ТьюрингаЯзык принадлежит классу NP, если существует детерминированная машина Тьюринга M и некоторый полином p(*) такие, что
Слово y называется обычно «подсказкой», «свидетелем» (witness), «доказательством» (proof).
Диаграмма «ближайших» классов сложности
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «NP» |
 |
||||
 |
||||||
 |
