Поліноміальна звідність

Будь-яка мова називається звідною за Карпом до мови , якщо існує функція , обчислювана за поліноміальний час, де F(x) належить в тому випадку, якщо x належить . Мова називається NP-складною, якщо до неї зводиться будь-яка мова класу NP, і називається NP-повною, якщо вона NP-складна і сама зводиться до класу NP. Якщо буде алгоритм, що розв'язує NP-повну задачу за поліноміальний час, тоді всі NP-задачі належать до класу P.

Розглянемо дві мови і над алфавітами і . Зведення до за Карпом — це функція , обчислювана за поліноміальний час, така, що . Таким чином, неформально мова «не складніше» від мови .

Якщо така функція існує, кажуть, що звідна за Карпом до і пишуть

Відзначимо, що зведення за Карпом є окремим випадком зведення за Куком. У англомовних джерелах також можна зустріти назву many-one reduction.

Клас мов PSPACE — множина мов, допустимих детермінованою машиною Тюрінга з поліноміальним обмеженням простору.

Клас мов NPSPACE — множина мов, допустимих недетермінованою машиною Тюрінга з поліноміальним обмеженням простору.

Транзитивність

Головною властивістю зведення за Карпом є транзитивність. Якщо уявити мови у вигляді символів, то можна розглядати як математичну операцію: Α>Β, Β>Ε → Α>Ε.

Див. також

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.