Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

NP-повна задача



План:


Введення

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


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

Алфавітом називається всяке кінцеве безліч символів (наприклад, {0,1} або {A, b, c} ). Безліч всіх можливих слів (кінцевих рядків, складених із символів цього алфавіту) над деякими алфавітом Σ позначається Σ * . Мовою L над алфавітом Σ називається всяке підмножина безлічі Σ * , Тобто L \ subset \ Sigma ^ * .

Завданням розпізнавання слова для мови L називається визначення того, чи належить дане слово мови L .

Мова L 1 називається зводиться (по Карпу) до мови L 2 , Якщо існує функція, f: \ Sigma ^ * \ to \ Sigma ^ * , Вичіслімих за полиномиальное час, і що має наступну властивість:

  • f (x) \ in L_2 тоді і тільки тоді, коли x \ in L_1 .

Зводиться по Карпу позначається як L_1 {\ le} _p L_2 або L_1 \ varpropto L_2 .

Мова L 2 називається NP-важким, якщо будь-яка мова з класу NP зводиться до нього. Мова називають NP-повним, якщо він NP-важкий, і при цьому сам лежить в класі NP.

Таким чином, якщо буде знайдений алгоритм, вирішальний деяку (яку) NP-повну задачу за полиномиальное час, то все NP-задачі опиняться в класі P, тобто будуть вирішуватися за полиномиальное час.


2. Гіпотеза P ≠ NP

Чи збігаються класи P і NP вже більше 30 років є відкритим питанням. Наукове співтовариство схиляється до негативної відповіді на це питання - в цьому випадку за полиномиальное час вирішувати NP-повні задачі не вдасться.

3. Приклади NP-повних задач


Примітки

  1. Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. Tetris is Hard, Even to Approximate - arxiv.org/abs/cs.CC/0210020 (Англ.) . preprint.

Література

  • Томас Х. Кормен та ін Глава 34. NP-повнота / / Алгоритми: побудова й аналіз = INTRODUCTION TO ALGORITHMS - 2-е вид. - М .: "Вільямс", 2006. - С. 1296. - ISBN 0-07-013151-1.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
AI-повна задача
21 NP-повна задача Карпа
Повна решітка
Повна категорія
Повна кривизна
Повна похідна функції
Повна група подій
Повна система (музика)
Крайова задача
© Усі права захищені
написати до нас