Сведение по Карпу | это... Что такое Сведение по Карпу? (original) (raw)

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

Рассмотрим два языка L_1 и L_2 над алфавитами $\Sigma$ и $\Gamma$ . Сведение к по Карпу — это функция $f\colon \Sigma^* \mapsto \Gamma^*$ , вычислимая за полиномиальное время, такая, что $\forall x \in L_1 \Leftrightarrow f(x) \in L_2$ . Таким образом, неформально язык L_1 «не сложнее» языка L_2 .

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

$L_1 \leqslant_K L_2.$

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

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

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

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

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

См. также

Понятие сведения. Список.

Ссылки

Курс «Введение в структурную теорию сложности»
Хопкфрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений, 2-е изд.: Пер. с англ. — М.: Издательский дом «Вильямс», 2002.
М. Н. Вялый, Сложность вычислительных задач — определение на функциях, без понятий «язык», «алфавит» и т. п.