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

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

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

См. также

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

Ссылки

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