Мы много знаем об ограничениях (полиномиального размера) контуров постоянной глубины. Поскольку формулы с постоянной глубиной (полиномиального размера) представляют собой еще более ограниченную модель вычислений, все известные проблемы, которых нет в AC 0 , также не могут быть вычислены с помощью...
Лучшая известная верхняя граница для временной сложности умножения - это оценка Мартина Фюрера , которая является более чем линейной сложностью сложения по времени. Есть ли у нас доказательство того, что сложение по сути проще, чем умножение?журнал nп 2O ( журнал*н )NжурналN2О(журнал*N)n\log...
Логический элемент И & ИЛИ - это логический элемент, который получает два входа и возвращает их И и ИЛИ. Могут ли схемы, выполненные только из логического элемента И & ИЛИ без разветвления, выполнять произвольные вычисления? Точнее, сводится ли пространство журналов вычислений за...
Есть ли вероятная гипотеза сложности / криптозащиты, которая исключает возможность того, что схемы полиномиального размера имеют субэкспоненциальный размер (т. Е. с ) ограниченной глубиной ( )...
Когда ограничение ограничено - входами, каждая -схема вычисляет некоторую функцию . Чтобы получить булеву функцию, мы можем просто добавить один пороговый вентиль fanin-1 в качестве выходного вентиля. На входе результирующая пороговая схема - выводит если , и выдает если ; порог может быть любым...
Многие важные результаты в теории вычислительной сложности и, в частности, в теории «структурной» сложности, обладают интересным свойством, которое можно понять как фундаментально следующее (как я вижу это ...) из алгоритмических результатов, дающих эффективный алгоритм или протокол связи для...
Рассмотрим следующие рассуждения: Пусть обозначим сложность Колмогорова из строки . Теорема Чайтена о неполноте гласит, чтохК( х )K(x)K(x)Иксxx для любой последовательной и достаточно сильной формальной системы , существует постоянную (зависящую только от формальной системы и ее языка), что для...
Используя алгоритм просмотра с переносом, мы можем вычислить сложение, используя полиномиальный размер семейства цепей 5 (или 4?) . Можно ли уменьшить глубину? Можем ли мы вычислить сложение двух двоичных чисел, используя семейство схем полиномиального размера с глубиной, меньшей глубины,...
Классический результат состоит в том, что каждая схема 2 вентилятора И-ИЛИ-НЕ, которая вычисляет PARITY из входных переменных, имеет размер не менее и это является резким. (Мы определяем размер как число логических элементов И и ИЛИ.) Доказательством является устранение гейта, и, похоже, оно...
(Фон Нейман дал алгоритм, который имитирует честную монету при доступе к одинаковым смещенным монетам. Алгоритм потенциально требует бесконечного числа монет (хотя в ожидании достаточно конечного числа). Этот вопрос касается случая, когда допустимое количество бросков монет ограниченная.)...
преамбула Интерактивные системы доказательства и протоколы Артура-Мерлина были введены Голдвассером, Микали, Ракоффом и Бабаем еще в 1985 году. Сначала считалось, что первый более мощный, чем второй, но Голдвассер и Сипсер показали, что они обладают одинаковой силой ( в отношении признания языка)....
N CNC\mathsf{NC} отражает идею эффективного распараллеливания, и одна из его интерпретаций - это проблемы, которые разрешимы во времени с использованием параллельных процессоров для некоторых констант , . У меня вопрос, есть ли аналогичный класс сложности, где время равно а число процессоров - ....
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Теперь определим множества всех входов со сложностью Колмогорова и определим последовательность Здесь - средняя последовательность времени...
Как известно, -clique функция принимает ( охватывающий ) подграф полного -vertex графа и выходов тогда и только тогда содержит -clique . Переменные в этом случае соответствуют краям от . Известно (Разборов, Алон-Боппана), что для эта функция требует монотонных схем размером около . kkkG ⊆ K n n K n...
В параметризованной сложности, . Предполагается, что каждое из условий является правильным.⊆ W [ 2 ] ⊆ … ⊆ W [ P ]FPT⊆W[1]FPT⊆W[1]\mathsf{FPT} \subseteq \mathsf{W}[1] ⊆W[2]⊆W[2]\subseteq \mathsf{W}[2] ⊆…⊆W[P]⊆…⊆W[P]\subseteq \ldots \subseteq \mathsf{W}[P] Если то .P = W [ P...
В статье «Сборник задач, завершенных для P» Гринлоу, Гувера и Руццо (PS) (PDF) , есть список проблем в P, которые, как известно, не находятся в NC и также не известны как P-полные. , (Этот список включает все открытые проблемы в превосходном обзоре Карпа и Рамачандрана .) Список открытых проблем...
Обсуждение : В последнее время я проводил некоторое личное время, изучая различные вещи в сложности общения. Например, я повторно ознакомился с соответствующей главой в Арора / Барак, начал читать некоторые статьи и заказал книгу Кушилевица / Нисана. Интуитивно я хочу сравнить сложность...
Теорема Карпа – Липтона утверждает, что если , то P H разрушается до Σ P 2 . Следовательно, при условии разделения между Σ P 2 и Σ P 3 , никакая N P -полная проблема не будет принадлежать P / p o l y .N P ⊂ P / p o l yNP⊂P/poly\mathsf{NP} \subset \mathsf{P/poly}P...
Два связанных вопроса об ограниченных вычислениях глубины: 1) Предположим, что вы начинаете с n битов, и начинаться с бита i может быть 0 или 1 с некоторой вероятностью p (i) независимо. (Если это упрощает задачу, мы можем предположить, что все p (i) s равны 0,1 или 1/2.или даже то, что все они...
Предположим, у нас есть проблема, параметризованная вещественным параметром p, который «легко» решить, когда и «трудно», когда для некоторых значений , . p = p 1 p 0 p 1p=p0p=p0p=p_0p=p1p=p1p=p_1п0p0p_0п1p1p_1 Одним из примеров является подсчет спиновых конфигураций на графиках. Считая взвешенные...