Сложность схемы - это исследование схем с ограниченными ресурсами и функций, вычисляемых такими схемами.
В 1980-х годах Разборов, как известно, показал, что существуют явные монотонные булевы функции (такие как функция CLIQUE), которые требуют экспоненциально большого количества вентилей AND и OR для вычисления. Однако базис {AND, OR} над булевой областью {0,1} является лишь одним примером интересного...
Это вопрос о сложности схемы. (Определения внизу.) Яо и Бейгель-Таруи показали, что каждое семейство цепей размером имеет эквивалентное семейство цепей размером глубины два , где выходной вентиль является симметричной функцией, а второй уровень состоит из ворота вентилятора в. Это довольно...
Райан Уильямс только что опубликовал свою нижнюю границу для ACC , класса задач, которые имеют контуры постоянной глубины с неограниченным разветвлением и вентилями AND, OR, NOT и MOD_m для всех возможных m. Что особенного в воротах MOD_m? Они позволяют имитировать арифметику над любым кольцом Z_m....
Пусть AAA будет фиксированным положительным целым числом размером nnn бит. Разрешается предварительно обрабатывать это целое число соответствующим образом. Учитывая другое положительное целое число BBB размером mmm битов, какова сложность умножения ABABAB ? Обратите внимание, что у нас уже есть...
Несколько лет назад Джоэл Фридман сделал несколько работ, касающихся нижних границ цепей для когомологий Гротендика (см. Документы: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024. ). Принесло ли это направление мысли новое понимание булевой сложности, или это скорее...
Я думал, что поделюсь этим вопросом, так как он может быть интересен для других пользователей здесь. Предположим, что функция из однородного класса (например, ) также входит в небольшой неоднородный класс (например, A C 0 / p o l y , т. Е. Неоднородный A C 0 ), означает ли это, что функция...
Пусть - булева функция, и давайте подумаем о f как о функции от до . На этом языке разложение Фурье функции f является просто разложением функции f по квадратным свободным мономам. (Эти мономов образуют базис для пространства вещественных функций на . Сумма квадратов коэффициентов равна просто так...
В своей книге «Сложность булевых функций» Стасис Юкна упоминает (стр. 564), что Колмогоров считал, что каждый язык в P имеет цепи линейного размера. Никакой ссылки не упоминается, и я не могу ничего найти в Интернете. Кто-нибудь знает больше об...
В вычислительной сложности есть важное различие между монотонными и общими вычислениями, и знаменитая теорема Разборова утверждает, что 3-SAT и даже MATCHING не являются полиномами в модели монотонных булевых схем. Мой вопрос прост: есть ли квантовый аналог для монотонных цепей (или нескольких)?...
Какова сложность решения, вычисляет ли схема с n входными битами и n выходными битами перестановку { 0 , 1 } n ? другими словами, является ли каждая строка битов в { 0 , 1 } n выходом схемы для некоторого входа? Это похоже на проблему, которая была изучена, но я не могу найти никаких...
Извиняюсь за вопрос, который обязательно должен быть во многих стандартных ссылках. Мне любопытно точно вопрос в названии, в частности, я имею в виду булевы схемы, без ограничений по глубине. Я поместил «наименьшее» в кавычки, чтобы учесть, что существует множество разных классов, которые, как...
Недавно Райан Уилламс доказал, что конструктивность в естественном доказательстве неизбежно приводит к разделению классов сложности: и . N E X PNЕИксп\mathsf{NEXP}Т С0TС0\mathsf{TC}^{0} Конструктивность в естественном доказательстве - это условие, которому удовлетворяют все комбинаторные...
Вопрос: Какова самая известная нижняя граница размера формулы для явной функции в AC 0 ? Существует ли явная функция с нижней границей Ω(n2)Ω(n2)\Omega(n^2) ? Задний план: Как и большинство нижних границ, трудно найти нижние границы размера формулы. Меня интересуют нижние границы размера формулы...
РЕДАКТИРОВАТЬ (v2): в конце добавлен раздел о том, что я знаю о проблеме. РЕДАКТИРОВАТЬ (v3): Добавлено обсуждение пороговой степени в конце. Вопрос Этот вопрос в основном справочный запрос. Я не знаю много о проблеме. Я хочу знать, была ли предыдущая работа по этой проблеме, и если да, может ли...
В опросе Д. Бера, Ф. Грина и С. Гомера «Квантовые схемы малой глубины» (стр. 36 ACM SIGACT News, июнь 2007 г., том 38, № 2) я прочитал следующее предложение: Классическая версия (в которой вентили и имеют самое большее постоянное разветвление), очевидно, слабее, чем...
Многочлен является монотонной проекцией многочлена если = poly , и существует присваивание , что . Таким образом, можно заменить каждую переменную из на переменную или константу или так, чтобы полученный многочлен совпадал с . е(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n)m ( n ) π : { y 1 , … , y m } → { x...
Состояние наших знаний об общих арифметических схемах похоже на состояние наших знаний о булевых схемах, то есть у нас нет хороших нижних границ. С другой стороны, мы имеем экспоненциальный размер нижних границ для монотонных булевых цепей . Что мы знаем о монотонных арифметических схемах? У нас...
В свете недавней пропасти на глубине 3 результата (который, среди прочего, дает глубины 3 арифметическая схема дляп×попределителя надС), у меня следующие вопросы: Григорьев и Карпиньскидоказалв2Ом(п)нижняя граница для любой глубины-3 арифметической схемы вычислительной Определительп×пматрицы над...
Есть ли вероятная гипотеза сложности / криптозащиты, которая исключает возможность того, что схемы полиномиального размера имеют субэкспоненциальный размер (т. Е. с ) ограниченной глубиной ( )...
N CNC\mathsf{NC} отражает идею эффективного распараллеливания, и одна из его интерпретаций - это проблемы, которые разрешимы во времени с использованием параллельных процессоров для некоторых констант , . У меня вопрос, есть ли аналогичный класс сложности, где время равно а число процессоров - ....