В каком случае заведомо не существует псевдослучайных генераторов:

Использование генераторов псевдослучайных чисел является основой идеи:

Условие существования вероятностной машины Тьюринга и полинома , причем машина заведомо остановится за время, не превосходящее , определяет, что:

Из утверждения "вероятность того, что объекта с нужными свойствами не существует, меньше 1" следует, что:

Если существует вычисление, требующее памяти , то реализовать его можно обратимым способом с использованием памяти:

Элементарному преобразованию в квантовом случае соответствует определение:

В случае одного q-бита обнуление внедиагональных элементов можно получить, если применить оператор с вероятностью:

Перестановок на каком количестве бит является достаточным для реализации функции, заданной булевой схемой в полном базисе:

Какому классу принадлежит , если существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что Б имеет выигрышную стратегию (Б - игрок, имеющих имя "белые"):

Для любого классического вероятностного алгоритма, делающего не более обращений к оракулу (), существует подгруппа и соответствующая функция , для которой вероятность ошибки алгоритма:

"Если - разложение числа на взаимно простые множители, то существует взаимно однозначное соответствие между остатками от деления на и парами остатков от деления на и на " - утверждает: