Я знаю, что побитовые операции выполняются очень быстро на современных процессорах, потому что они могут работать на 32 или 64 битах параллельно, поэтому побитовые операции занимают только один такт. Однако сложение - это сложная операция, которая состоит как минимум из одной и, возможно, до дюжины...
Относительно квантовых ворот Тоффоли : это классически универсально, и если так, то почему? это квантово универсально и почему?
После выпуска библиотеки AIGER для обработки и инвертирования графов где-то в 2006 году (я думаю), некоторые схемы SAT решатели были выпущены в 2006-2008 годах, и в нескольких гонках / соревнованиях SAT были треки AIG. Однако с тех пор кажется, что основное внимание было уделено либо SMT, либо...
Я знаю, что шлюзы NAND можно использовать для создания схем, реализующих каждую таблицу истинности, а современные компьютеры состоят из вентилей NAND. Какова теоретическая связь между воротами NAND и полнотой Тьюринга? Мне кажется, что схемы затворов NAND ближе к конечным автоматам, чем машины...
Например, я знаю, что нерегулярный язык находится в A C 0 . Я хотел бы знать больше примеров, как
Я не могу обернуться вокруг того, как работает SR Latch. По-видимому, вы подключаете входную строку от R, а другую от S, и вы должны получить результаты в и .Q ′QQQQ'Q'Q' Однако и R, и S требуют ввода от выхода другого, а выход другого требует ввода от выхода другого. Что первично - курица или...
Определение P - это язык, который может быть определен алгоритмом полиномиального времени. Определение P / poly может означать язык, который может быть определен схемой полиномиального размера (см. Http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Теперь, почему нельзя за полиномиальное...
Хорошо известно, что каждая булева функция может быть реализована с использованием булевой схемы глубины 2 (над переменными, их отрицанием и постоянными значениями) содержащий логические элементы И на первом уровне и один логический элемент ИЛИ на верхнем уровне; это просто представление DNF из...