NL⊈PNL⊈P\mathsf{NL} \nsubseteq \mathsf{P} Теперь рассмотрят схему семьи с оракулом воротами - скажем, , где классе сложности схемы , содержащая logspace с доступом оракула к другому классу , через оракул ворот приложенного к основанию . Существуют ли какие-либо патологические примеры, похожие по...
Какие теоремы иерархии существуют для глубины контура? Заявления как если и то .g(n)∈o(f(n))g(n)∈o(f(n))g(n) \in o(f(n))f(n)∈nO(1)f(n)∈nO(1)f(n) \in n^{O(1)}SizeDepth(nO(1),g(n))⊊SizeDepth(nO(1),f(n))SizeDepth(nO(1),g(n))⊊SizeDepth(nO(1),f(n))\mathsf{SizeDepth}(n^{O(1)}, g(n)) \subsetneq...
У меня есть несколько вопросов, касающихся обмана контуров постоянной глубины. Известно, что независимость необходима для обмана A C 0 цепей глубины d , где n - размер входа. Как это можно доказать?журналO ( д)( н )журналО(d)(N)\log^{O(d)}(n)A C0AС0AC^0dddNNn Поскольку вышеприведенное верно, любой...
Я читаю знаменитую статью Impagliazzo и Wigderson в 1997 году. Так как я новичок в этой области, и эта статья является краткой версией конференции, мне трудно следить за их доказательствами. В частности, некоторые из их новых теорем не имеют доказательств. Насколько мне известно, не было...
Предположим, что наш вход является двоичным и мы должны вывести , где - некоторое постоянное целое число. Это просто сдвиг, если является степенью двойки, но как насчет других чисел? Можем ли мы сделать это с контуром постоянной глубины для каждого ? Как насчет ?⌊ x / c ⌋ c c c c = 3Иксxx⌊ х / с...
Фон Сложность схемы определяется как набор семейств схем (т. Е. Последовательности схем, по одной для каждого входного размера) ограниченной глубины и полиномиального размера, построенных с использованием неограниченного разветвления И, ИЛИ и НЕ.A C0AC0AC^0 Функция четности с n- битным входом равна...
Монотонная формула CNF с m членами на n переменных ( ) - это формула вида , где каждый является ИЛИ некоторого подмножества переменных и находятся в диапазоне от до . f ( x 1 , … , x n ) = ⋀ C i C i x 1 , … , x n i 1 мИкс1, … , ХNИкс1,...,ИксNx_1,\ldots,x_nе( х1, … , ХN) = ⋀ Cяе(Икс1,...,ИксN)знак...
Мой вопрос заключается в том, почему нижние оценки для логических схем глубины 3 с логическими элементами "и" и "xor" для определителя не подразумевают такие же нижние оценки для арифметических схем над ?ZZ\mathbb{Z} Что не так со следующим аргументом: Пусть - определитель, вычисляющий...
Следующий вопрос связан с оптимальностью алгоритма динамического программирования Беллмана-Форда - кратчайшего пути (см. Этот пост для связи). Кроме того, положительный ответ будет означать, что минимальный размер монотонной недетерминированной программы ветвления для задачи STCONN равен . t Θ ( n...
Рассмотрим непустой язык двоичных строк длины . Я могу описать булевой схемой с входами и одним выходом, так что истинно тогда и только тогда, когда : это хорошо известно.LLLnnnLLLCCCnnnC(w)C(w)C(w)w∈Lw∈Lw \in L Тем не менее, я хочу представлять с булевой схемой с выходами и определенным...
Класс NCiNCi\textrm{NC}^i является классом функций, вычисляемых семействами схем ограниченного вкручивания, размера nO(1)nO(1)n^{O(1)} и глубины O(logi(n))O(logi(n))O(\log^i(n)) . NCNC\textrm{NC} -hierarchy является объединением этих классов. Есть ли какое-либо исследование линейного размера этой...
Минимизация схемы - это проблема минимизации размера данной схемы. Есть ли что-нибудь подобное для общих программ? В частности, мой вопрос - Существуют ли алгоритмы, чтобы минимизировать количество инструкций для данной программы. Я знаю, что это неразрешимая проблема, но я не ищу решение, которое...
Рассмотрим следующую проблему: Учитывая матрицу мы хотим оптимизировать количество сложений в алгоритме умножения для вычисления v ↦ M v .MMMv↦Mvv↦Mvv \mapsto Mv Я нахожу эту проблему интересной из-за ее связи со сложностью умножения матриц (эта проблема является ограниченным вариантом умножения...
Предположим, у меня есть логическая схема СCC это вычисляет некоторую функцию е: { 0 , 1}N→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}, Предположим, что схема состоит из логических элементов И, ИЛИ и НЕ с максимальным и минимальным разветвлениями 2. Позволять x ∈ { 0 , 1}Nx∈{0,1}nx \in...
Пусть некоторый класс сложности и BP- C быть рандомизированное аналог C определяется как БПП по отношению к P . Более формально мы предоставляем полиномиально много случайных битов и принимаем входные данные, если вероятность принять больше...
Я заинтересован в определении сложности следующей задачи решения: учитывая два целых числа и l 2 (каждое из которых содержит не более m бит), решить, является ли старший значащий бит умножения l 1 ⋅ l 2 равным 1 (где результат печатается в 2м битах с возможно ведущими 0)?L1L1l_1L2L2l_2L1⋅...
DLOGTIME определяется по адресу http://en.wikipedia.org/wiki/DLOGTIME определяется по адресу http://en.wikipedia.org/wiki/L_%28complexity%29 и определены по адресу http://en.wikipedia.org/wiki/NC_%28complexity%29 LL\operatorname{L} Северная КаролинаNC\operatorname{NC}Северная...
Алгоритм Берковица обеспечивает схему полиномиального размера с логарифмической глубиной для определителя квадратной матрицы с использованием степеней матрицы. Алгоритм неявно использует отмену. Является ли аннулирование необходимым для получения схемы полиномиального размера с логарифмической или...
Скажем, у нас есть булева функция f:{−1,1}n→{−1,1}f:{−1,1}n→{−1,1}f:\{-1,1\}^n\rightarrow \{-1,1\} и мы применяем δδ\deltaслучайное ограничение на fff, Кроме того, скажем, что дерево решенийTTT это вычисляет fff сжимается до размера O(1)O(1)O(1)в результате случайного ограничения. Означает ли это,...
Я считаю , что ответы на этот вопрос зависит классы дают такое , что для всех полиномов , существует проблема в классе , который не имеет схемы размера . Однако я спрашиваю о размере схемы .pppp(n)p(n)p(n)ω(n)ω(n)\omega \hspace{.02 in}(n)...