Багатозначна зводимість
У теорії обчислюваності та теорії обчислювальної складності, багатозначна зводимість являє собою зводимість, що перетворює приклади одної задачі розпізнавання у приклади другої задачі розпізнавання. Зводимості, таким чином, використовуються для вимірювання відносної обчислювальної важкості двох задач.
Багатозначні зводимості є частинним випадком та посиленою формою зводимостей за Тюрінгом. Для багатозначних зводимостей оракул може бути викликаний тільки одного разу наприкінці і відповідь не може бути змінена.
Багатозначні зводимості були вперше використані Емілем Постом у 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.