Багатозначна зводимість

У теорії обчислюваності та теорії обчислювальної складності, багатозначна зводимість являє собою зводимість, що перетворює приклади одної задачі розпізнавання у приклади другої задачі розпізнавання. Зводимості, таким чином, використовуються для вимірювання відносної обчислювальної важкості двох задач.

Багатозначні зводимості є частинним випадком та посиленою формою зводимостей за Тюрінгом. Для багатозначних зводимостей оракул може бути викликаний тільки одного разу наприкінці і відповідь не може бути змінена.

Багатозначні зводимості були вперше використані Емілем Постом у 1944 році. Пізніше Норман Шапіро використав ідентичне поняття у 1956 році під назвою сильна зводимість.

Посилання

• E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society 50 (1944) 284-316
• Norman Shapiro, "Degrees of Computability", Transactions of the American Mathematical Society 82, (1956) 281-299