Вопросы с тегом «circuit-complexity»

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

18
Самый эффективный способ преобразовать цепь

РЕДАКТИРОВАТЬ (22 августа 2011 г.): Я еще больше упрощаю вопрос и назначаю вознаграждение за этот вопрос. Возможно, на этот более простой вопрос будет легко ответить. Я также собираюсь зачеркнуть все части оригинального вопроса, которые больше не актуальны. (Спасибо Стасису Юкне и Райану О'Доннелу...

17
Лучше нижние оценки, чем 3n для небулевых функций?

Нижняя граница Блума 3n−o(n)3N-о(N)3n-o(n) - это лучшая известная нижняя граница схемы по полному базису для явной функции f:{0,1}n→{0,1}f:{0,1}n→{0,1}f : \{0,1\}^n \to \{0,1\} , ср. Юкна ответ на этот вопрос для связанных результатов. Каковы наиболее известные нижние оценки, если диапазон fff...

17
Булевы функции, где чувствительность равна блочной чувствительности

Некоторая работа по чувствительности против чувствительности блоков была направлена ​​на изучение функций с максимально большим промежутком между и , чтобы развить гипотезу, что только полиномиально больше, чем . Как насчет противоположного направления? Что известно о функциях, где...

17
Пример, демонстрирующий силу недетерминированных цепей

Недетерминированная логическая схема имеет, помимо обычных входов , набор «недетерминированных» входов . Недетерминированная схема принимает вход если существует такой, что выход схемы включен . Аналогично (класс языков, разрешимых схемами полиномиального размера), можно определить как класс...

17
PARITY в QAC_0 (если это имеет смысл)

Как хорошо известно, PARITY не может быть выполнено в многоразмерных схемах с постоянной глубиной, и на самом деле схемы с постоянным углублением требуют количества входов EXP. А как насчет схем QUANTUM? а) Можно ли выполнить PARITY с помощью квантового контура, который имеет постоянную глубину и...

17
Состояние нижних границ контуров для контуров глубины, ограниченных полилогом

Сложность схемы с ограниченной глубиной является одной из основных областей исследования в теории сложности схемы. Эта тема имеет происхождение в результатах типа «функция четности не в » и « функция mod не вычисляется », где - класс языков, разрешимых по неоднородности, постоянной глубине,...

17
Нижние оценки для размера недетерминированных цепей

Известно, что минимальный размер цепей, функцию четности, в точности равен . Нижняя оценка доказательства основана на методе исключения ворот.U2U2U_23 ( n - 1 )3(N-1)3(n-1) Недавно я заметил, что метод исключения затвора хорошо работает и для недетерминированных цепей, и мы можем доказать нижнюю...

16
Количество двоичных элементов, необходимых для одновременного вычисления И и ИЛИ из n входных битов

Какое минимальное количество двоичных вентилей необходимо для вычисления И и ИЛИ из входных битов одновременно? Тривиальная верхняя граница . Я считаю, что это оптимально, но как это доказать? Стандартный метод устранения строба здесь не работает, так как, присваивая константу любой из входных...

16
Какие

Знаменитая картина мира Нила Иммермана выглядит следующим образом (нажмите, чтобы увеличить):                                         Его «действительно выполнимый» класс не включает другого класса; мой вопрос тогда: Что такое проблема AC 0, которая считается непрактичной и почему?...

16
Является ли BPP vs. P реальной проблемой после того, как мы знаем, что BPP лежит в P / poly?

Мы знаем (на данный момент около 40 лет, спасибо Адлеману, Беннету и Джиллу), что включение BPP P / poly и еще более сильное BPP / poly P / poly имеют место. «/ Poly» означает, что мы работаем неравномерно (отдельная схема для каждой входной длины ), в то время как P без этой «/ poly» означает, что...

16
Оракулярное разделение между много- и логарифмическими квантовыми цепями

Следующая проблема появляется в списке Ааронсона « Десять полуградовых вызовов для теории квантовых вычислений» . IsB Q P = B P PB Q N CВQпзнак равноВппВQNС\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} р о л у л о г (п) В В Р В Р Р Б В Н С Другими словами, может ли «квантовая» часть любого квантового...

16
Более сильные понятия униформизации?

Единственный пробел, который я всегда осознавал, что я на самом деле не понимаю, - это неравномерная и равномерная вычислительная сложность, где сложность схемы представляет собой неоднородную версию, а машины Тьюринга - это вещи, которые являются однородными. Я предполагаю, что «равномерный» - это...

15
Барьеры и сложность монотонной цепи

Естественное доказательство является препятствием для доказательства нижних оценок сложности схемы булевых функций. Они напрямую не подразумевают такого барьера в доказательстве нижних границ сложности схемы. Есть ли прогресс в выявлении таких барьеров? Есть ли другие барьеры в монотонной...

15
Характеристика одноразовых формул по полному двоичному базису

Фон Формула однократного чтения для набора элементов (также называемая базисом) - это формула, в которой каждая входная переменная появляется один раз. Формулы однократного чтения обычно изучаются на основе де Моргана (которая имеет 2-битные логические элементы И и ИЛИ, и 1-битный вентиль НЕ) и...

15
наименьший размер цепи с использованием вентилей XOR

Предположим, нам дан набор из n булевых переменных x_1, ..., x_n и набора из m функций y_1 ... y_m, где каждый y_i является XOR (заданного) подмножества этих переменных. Цель состоит в том, чтобы вычислить минимальное количество операций XOR, которое необходимо выполнить для вычисления всех этих...

15
Поддержание порядка в списке в за раз

Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...

15
Известно ли, что существуют функции со следующим свойством прямой суммы?

Этот вопрос может быть задан либо в рамках сложности схем булевых схем, либо в рамках теории алгебраической сложности, либо, вероятно, во многих других ситуациях. Подсчитав аргументы, легко показать, что на N входах существуют булевы функции, для которых требуется экспоненциально много гейтов...

15
Случайная монотонная функция

В статье Разборова-Рудича « Естественные доказательства» , стр. 6, в той части, в которой они обсуждают, что есть «сильные доказательства нижних границ против моделей монотонных схем» и как они вписываются в картину, есть следующие предложения: Здесь проблема не в конструктивности - все свойства,...