ВАШЕ СВИДЕТЕЛЬСТВО
О ПУБЛИКАЦИИ В СМИ И РЕЦЕНЗИЯ
бесплатно за 1 минуту
Добавить материал
×
Медианары для учителей с выдачей свидетельства
Количество Ваших материалов: 0.
Авторское
свидетельство о публикации в СМИ
добавьте 1 материал
Свидетельство
о создании электронного портфолио
добавьте 5 материала
Секретный
подарок
добавьте 10 материалов
Грамота за
информатизацию образования
добавьте 12 материалов
Рецензия
на любой материал бесплатно
добавьте 15 материалов
Видеоуроки
по быстрому созданию эффектных презентаций
добавьте 17 материалов
Ахмед Изнауров свидетельство о публикации рецензия
‘видетельство о публикации скачивание доступно только автору
Свидетельство Скачивание доступно только автору
Классы P и NP

Классы P и NP

  • Научно-исследовательская работа
  • Научные работы
  • Образовательные программы
  • Повышение квалификации
  • Подготовка к тестированию
  • Информатика
  • Высшее образование

В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество задач распознавания (англ.), решение которых при наличии некоторых дополнительных сведений (так называемого сертификата решения) можно «быстро» (за время, не превосходящее полинома от размера данных) проверить на машине Тьюринга. Эквивалентно класс NP можно определить как содержащий задачи, которые можно «быстро» решить на недетерминированной машине Тьюринга. Класс сложности NP определяется для множества языков, то есть множеств слов над конечным алфавитом . Язык L называется принадлежащим классу NP, если существуют двуместный предикат из класса P (то есть вычислимый за полиномиальное время) и константа такие, что для всякого слова x условие «xпринадлежит L» равносильно условию «найдётся y длины меньше такой, что верно » (где |x| — длина слова x). Слово y называется сертификатомпринадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L.


Все файлы материала: