Перейти до вмісту

Клас складності NP

Матеріал з Вікіпедії — вільної енциклопедії.
Версія від 13:47, 2 березня 2022, створена InternetArchiveBot (обговорення | внесок) (Bluelink 1 book for Перевірність (20220301)) #IABot (v2.0.8.6) (GreenC bot)

Клас складності NP (англ. Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що .[1]

Формальне визначення

Мова належить до класу NP (недетермінованих поліноміальних) якщо вона розпізнається недетермінованою машиною Тюрінга з поліноміальною часовою складністю .[2]

Властивості

Оскільки кожна детермінована машина Тюринга може розглядатись як недетермінована, але без вибору варіантів кроків, то клас є підмножиною . Однак до класу складності NP належить багато інших задач, належність яких до класу P не доведена.[2]

Однією з найгостріших задач математики є з'ясування вірності тотожності . Тобто, пошуку відповіді на питання, чи є правильним твердження, що будь-що, що виконує недетермінована машина Тюринга за поліноміальний час можна виконати на детермінованій машині за, можливо більший, поліноміальний час.

Приклад задач

До задач класу складності NP належать:[3]

  • Розв'язність логічного виразу.
  • Триколірне розфарбування графу.
  • Побудова кліки з вершин на неорієнтованому графі.
  • Покриття множин: нехай задане сімейство підмножин деякої множини ; необхідно знайти підсемейство із , так, що:
  • Розбиття множин: за попередніх умов, але, крім того, вимагається, щоб (для довільних з ).
  • Існування гамільтонового циклу на неорієнтованому графі.
  • Задача пакування рюкзака: для змінних , що приймають значення 0 та 1 розв'язати рівняння:
    де та  — наперед задані цілі числа.
    для загального випадку, ця задача є розв'язанням діофантового рівняння.
  • Розбиття на дві частини: нехай дано чисел з , необхідно розбити на дві множини та що не перетинаються, так, щоб:
  • Задача комівояжера[4].

Посилання

  1. Рейнгольд, Нивергельт Ю., Део Н. (1980). Комбинаторные Алгоритмы (рос.) . Москва: Мир. с. 444.
  2. а б John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages and Computation (англ.) (вид. 2). Addison-Wesley. с. 419. ISBN 0-201-44124-1.
  3. Лорьер Ж.-Л. (1991). Системы искусственного интеллекта. пер. с фр. Мир.
  4. Adleman, Leonard M. Molecular computation of solutions to combinatorial problems.

Див. також