Вопросы с тегом «upper-bounds»

43
Лучшие верхние границы на SAT

В другой ветке Джо Фитцсимонс спросил о «лучших текущих нижних границах на 3SAT». Я хотел бы пойти по другому пути: каковы лучшие текущие верхние границы на 3SAT? Другими словами, какова временная сложность наиболее эффективного SAT-решателя? В частности, возможно ли найти субэкспоненциальный (но...

40
Фиксированная глубина характеристики ? ?

Это вопрос о сложности схемы. (Определения внизу.) Яо и Бейгель-Таруи показали, что каждое семейство цепей размером имеет эквивалентное семейство цепей размером глубины два , где выходной вентиль является симметричной функцией, а второй уровень состоит из ворота вентилятора в. Это довольно...

21
Может ли сложение выполняться на глубине менее 5?

Используя алгоритм просмотра с переносом, мы можем вычислить сложение, используя полиномиальный размер семейства цепей 5 (или 4?) . Можно ли уменьшить глубину? Можем ли мы вычислить сложение двух двоичных чисел, используя семейство схем полиномиального размера с глубиной, меньшей глубины,...

17
Каковы пределы вычислений в этой вселенной?

Я понимаю, что полнота Тьюринга требует неограниченной памяти и неограниченного времени. Однако в этом сервисе существует ограниченное количество атомов, что ограничивает память. Например, даже если иррационально, нет способа сохранить более определенного числа цифр, даже если все атомы во...

14
Какую ширину дерева может иметь дерево плюс половина ребер?

Пусть G дерево на 2n вершинах. Ширина дерева G, tw (G) = 1. Теперь предположим, что мы добавляем n ребер в G, чтобы получить граф H. Легкая верхняя граница для tw (H) равна n + 1. Является ли это по существу наилучшим возможным? Как-то кажется, что tw (H) должно быть O (sqrt (n)), но это лишь...

14
Сложность OR-схемы плотного линейного оператора

Рассмотрим следующую простую модель монотонной схемы: каждый элемент - это просто двоичное ИЛИ. Какова сложность функции где - булева матрица с 0? Может ли он быть рассчитан по линейным размерам OR-цепей?f ( x ) = A x f(x)=Axf(x)=AxA AAn × n n×nn \times nO ( n )O(n)O(n) Более формально, является...

10
Каковы текущие наиболее известные верхние и нижние границы порога (не) выполнимости для случайных k-sat и / или 3-sat?

Я хотел бы знать текущее состояние фазового перехода для случайных k-sat, учитывая n переменных и m предложений, что является наиболее известным c = m / n для верхней и нижней...

10
Являются ли схемы квазиполиномиального размера для 3-SAT тривиальными?

Предположим, что мы рассматриваем 3-SAT с переменными и c предложениями. Я исследую метод, который, по-видимому, использует O ( v 2 + log c ) время / пространство для решения любой задачи SAT, соответствующей данному описанию, с точностью до ошибки, которую можно скорректировать до произвольной...

10
Почти 2-SAT NP-жесткий?

Сложна ли задача NPF SAT NP, когда общее число (но не ширина) предложений из 3 или более членов ограничено сверху константой? А что конкретно, когда есть только один такой...

9
Точная сложность проблемы в

Позволять xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\} за i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}с обещанием, что x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\} (где сумма закончилась ZZ\mathbb{Z}). Тогда какова сложность определения, еслиx=1x=1x = 1? Обратите внимание, что...