Используя алгоритм просмотра с переносом, мы можем вычислить сложение, используя полиномиальный размер семейства цепей 5 (или 4?) . Можно ли уменьшить глубину? Можем ли мы вычислить сложение двух двоичных чисел, используя семейство схем полиномиального размера с глубиной, меньшей глубины,...
Предположим, что граф с вершинами представлен как поток из ребер, но допускается несколько проходов по потоку.н мграммGGNnnмmm Моника Раух Хензингер, Прабхакар Рагхаван и Шридар Раджагопалан отметили, что пространство необходимо, чтобы определить, существует ли путь между двумя заданными вершинами...
[Примечание: я полагаю, что этот вопрос никоим образом не зависит от правильности или неправильности статьи Деолаликара.] В блоге Скотта Ааронсона « Оптимизированный Штетл» в дискуссии о недавней попытке Деолаликара на P против NP Леонид Гурвиц сделал следующий комментарий : Я попытался понять /...
Четность и подобны неразлучным близнецам. Или так казалось за последние 30 лет. В свете результатов Райана возобновится интерес к маленьким классам.AC0AC0AC^0 Faxst Saxe Sipser от Yao до Hastad - это все паритетные и случайные ограничения. Разборов / Смоленский является приближенным полиномом с...
Фон: Рассмотрим обычную двухстороннюю модель сложности коммуникации, где Алисе и Бобу даны битные строки и и они должны вычислить некоторую булеву функцию , где .nnnxxxyyyf(x,y)f(x,y)f(x,y)f:{0,1}n×{0,1}n→{0,1}f:{0,1}n×{0,1}n→{0,1}f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\} Мы определяем следующие...
USTCONN - это проблема, которая требует решения о том, существует ли путь от исходной вершины sss до целевой вершины ttt в графе GGG , где все они представлены как часть входных данных. Омер Рейнгольд показал, что USTCONN находится в L (doi: 10.1145 / 1391289.1391291 ). Доказательство создает...
РЕДАКТИРОВАТЬ (22 августа 2011 г.): Я еще больше упрощаю вопрос и назначаю вознаграждение за этот вопрос. Возможно, на этот более простой вопрос будет легко ответить. Я также собираюсь зачеркнуть все части оригинального вопроса, которые больше не актуальны. (Спасибо Стасису Юкне и Райану О'Доннелу...
Рассмотрим язык different состоящий из всех строк k- букв над Σ, таких, что никакие две буквы не равны:L k - d i s t i n c tLk−distinctL_{k-distinct}kkΣ\Sigma L k - d i s t i n c t : = { w = σ 1 σ 2 . , , σ к | ∀ я ∈ [ к ] : σ я ∈ Е и ∀ J ≠ я : σ J ≠ σ я...
Я думаю, что теорема об иерархии размеров для сложности схемы может быть главным прорывом в этой области. Это интересный подход к разделению классов? Мотивация вопроса заключается в том, что мы должны сказать есть некоторая функция, которая не может быть вычислена схемами размера и может быть...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Определим Gaussian сложность в качестве матрицы , чтобы минимальное число элементарных операций строк и столбцов , необходимых для приведения матрицы в верхней треугольной форме. Это величина от до (через гауссовское исключение). Понятие имеет смысл в любой области.n×nn×nn \times nn 2000n2n2n^2 Эта...
Статья Фишера за этот месяц напомнила мне, как мало я знаю об искусстве кратких структур данных и алгоритмах их использования. Для тех, кто не знает о сжатых структурах данных: Учитывая комбинаторную структуру, с (n) различными конфигурациями и известным «полезным» представлением . Существует ли...
Нижняя граница Блума 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...
Сложность схемы с ограниченной глубиной является одной из основных областей исследования в теории сложности схемы. Эта тема имеет происхождение в результатах типа «функция четности не в » и « функция mod не вычисляется », где - класс языков, разрешимых по неоднородности, постоянной глубине,...
Какое минимальное количество двоичных вентилей необходимо для вычисления И и ИЛИ из входных битов одновременно? Тривиальная верхняя граница . Я считаю, что это оптимально, но как это доказать? Стандартный метод устранения строба здесь не работает, так как, присваивая константу любой из входных...
Недавно я обнаружил квадратичную нижнюю границу сложности задачи в модели дерева решений, и мне интересно, можно ли частично обобщить этот результат в модели машины с произвольным доступом. Под частичностью я подразумеваю обобщение программ ОЗУ с определенным временным / пространственным...
(Обобщенная) высота звезды в языке - это минимальная вложенность звезд Клини, необходимая для представления языка расширенным регулярным выражением. Напомним, что расширенное регулярное выражение над конечным алфавитом удовлетворяет следующему:AAA (1) и - расширенные регулярные выражения для...
Фон Формула однократного чтения для набора элементов (также называемая базисом) - это формула, в которой каждая входная переменная появляется один раз. Формулы однократного чтения обычно изучаются на основе де Моргана (которая имеет 2-битные логические элементы И и ИЛИ, и 1-битный вентиль НЕ) и...
Это продолжение этого вопроса и связано с этим вопросом Шивы Кинали. Кажется, что доказательства в этих работах ( Аллендер , Кауссин-Маккензи-Териен-Фольмер , Койран-Перифель ) используют теоремы иерархии. Я хочу знать, являются ли доказательства « чистыми » теоремами диагонализации или они...
Каждая монотонная арифметическая схема , то есть -цепь, вычисляет некоторый многомерный многочлен с неотрицательными целыми коэффициентами. Учитывая полином , схема{+,×}{+,×}\{+,\times\}f ( x 1 , … , x n )F(x1,…,xn)F(x1,…,xn)F(x_1,\ldots,x_n)f(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n) вычисляет если...