|
Багатозначна зводимістьУ теорії обчислюваності та теорії обчислювальної складності, багатозначна зводимість являє собою зводимість, що перетворює приклади одної задачі розпізнавання у приклади другої задачі розпізнавання. Зводимості, таким чином, використовуються для вимірювання відносної обчислювальної важкості двох задач. Багатозначні зводимості є частинним випадком та посиленою формою зводимостей за Тюрінгом. Для багатозначних зводимостей оракул може бути викликаний тільки одного разу наприкінці і відповідь не може бути змінена. Багатозначні зводимості були вперше використані Емілем Постом у 1944 році. Пізніше Норман Шапіро використав ідентичне поняття у 1956 році під назвою сильна зводимість. Посилання
|