Изменения

Перейти к: навигация, поиск

Вычисления с оракулом

188 байт убрано, 22:55, 8 июня 2012
Отмена правки 24461 участника 178.252.68.68 (обсуждение)
{{Определение
|definition=
Будем называть '''оракулом''' для языка Оракул — абстракция , вычисляющая за <tex>AO(1)</tex> абстрактное вычислительное устройствовремени, для которого постулируется возможность решить задачу о принадлежности некоторого слова языку верно ли, что <tex>Ax</tex> за принадлежит множеству <tex>O(1)A</tex> времени.
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/24465»

Навигация