Полиномиальная сводимость

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Любой язык называется сводимым по Карпу к языку , если существует функция , вычисляемая за полиномиальное время, где F(x) принадлежит в том случае, если x принадлежит . Язык называется NP-трудным, если к нему сводится любой язык NP класса, и называется NP-полным, если он NP-труден и сам сводится к NP классу. Если будет алгоритм, решающий NP-полную задачу за полиномиальное время, тогда все NP-задачи относятся к классу P.

Рассмотрим два языка и над алфавитами и . Сведение к по Карпу — это функция , вычислимая за полиномиальное время, такая, что . Таким образом, неформально язык «не сложнее» языка .

Если такая функция существует, говорят, что сводима по Карпу к и пишут

Отметим, что сведение по Карпу является частным случаем сведения по Куку. В англоязычных источниках также можно встретить название en:many-one reduction.

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

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

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

[править | править код]

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