Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
У теорії обчислюваності та теорії обчислювальної складності, багатозначна зводимість являє собою , що перетворює приклади одної у приклади другої задачі розпізнавання. Зводимості, таким чином, використовуються для вимірювання відносної обчислювальної важкості двох задач.
Багатозначні зводимості є частинним випадком та посиленою формою . Для багатозначних зводимостей оракул може бути викликаний тільки одного разу наприкінці і відповідь не може бути змінена.
Багатозначні зводимості були вперше використані Емілем Постом у 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi obchislyuvanosti ta teoriyi obchislyuvalnoyi skladnosti bagatoznachna zvodimist yavlyaye soboyu sho peretvoryuye prikladi odnoyi u prikladi drugoyi zadachi rozpiznavannya Zvodimosti takim chinom vikoristovuyutsya dlya vimiryuvannya vidnosnoyi obchislyuvalnoyi vazhkosti dvoh zadach Bagatoznachni zvodimosti ye chastinnim vipadkom ta posilenoyu formoyu Dlya bagatoznachnih zvodimostej orakul mozhe buti viklikanij tilki odnogo razu naprikinci i vidpovid ne mozhe buti zminena Bagatoznachni zvodimosti buli vpershe vikoristani Emilem Postom u 1944 roci Piznishe vikoristav identichne ponyattya u 1956 roci pid nazvoyu silna zvodimist PosilannyaE 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