Теоретическая информатика предоставила несколько примеров «цены абстракции». Два самых выдающихся из них - это устранение и сортировка по Гауссу. А именно: Известно, что исключение Гаусса является оптимальным для, скажем, вычисления определителя, если вы ограничиваете операции строками и столбцами...
При разработке алгоритма для новой задачи, если я не смогу найти алгоритм полиномиального времени через некоторое время, я мог бы попытаться доказать, что он NP-сложный. Если мне это удастся, я объяснил, почему я не смог найти алгоритм полиномиального времени. Не то, чтобы я точно знал, что P! =...
Каковы лучшие нижние границы тока для времени и глубины цепи для
В другой ветке Джо Фитцсимонс спросил о «лучших текущих нижних границах на 3SAT». Я хотел бы пойти по другому пути: каковы лучшие текущие верхние границы на 3SAT? Другими словами, какова временная сложность наиболее эффективного SAT-решателя? В частности, возможно ли найти субэкспоненциальный (но...
Это вопрос о сложности схемы. (Определения внизу.) Яо и Бейгель-Таруи показали, что каждое семейство цепей размером имеет эквивалентное семейство цепей размером глубины два , где выходной вентиль является симметричной функцией, а второй уровень состоит из ворота вентилятора в. Это довольно...
В 1980-х годах Разборов, как известно, показал, что существуют явные монотонные булевы функции (такие как функция CLIQUE), которые требуют экспоненциально большого количества вентилей AND и OR для вычисления. Однако базис {AND, OR} над булевой областью {0,1} является лишь одним примером интересного...
Пусть PRIMES (иначе тестирование на примитивность ) будет проблемой: Учитывая натуральное число , является простое число?NNnNNn Пусть FACTORING будет проблемой: Учитывая натуральные числа , с , имеет ли фактор с ?NNnммm1 ≤ m ≤ n1≤м≤N1 \leq m \leq nNNnddd1 < д< м1<d<м1 < d < m Известно...
Жадность, из-за отсутствия лучшего слова, это хорошо. Одной из первых алгоритмических парадигм, изучаемых в курсе вводных алгоритмов, является жадный подход . Жадный подход приводит к простым и интуитивно понятным алгоритмам для многих задач в P. Более интересно, что для некоторых NP-трудных задач...
Несколько лет назад Джоэл Фридман сделал несколько работ, касающихся нижних границ цепей для когомологий Гротендика (см. Документы: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024. ). Принесло ли это направление мысли новое понимание булевой сложности, или это скорее...
Недавний результат оценки нижнего предела сложности схемы Райана Уильямса предоставляет метод доказательства, который использует результат верхнего предела для доказательства нижних границ сложности. Суреш Венкат в своем ответе на этот вопрос : есть ли какие-то противоречивые результаты в...
Пусть - булева функция, и давайте подумаем о f как о функции от до . На этом языке разложение Фурье функции f является просто разложением функции f по квадратным свободным мономам. (Эти мономов образуют базис для пространства вещественных функций на . Сумма квадратов коэффициентов равна просто так...
Мне нужно рассчитать бегущую медиану: Ввод: , , вектор .k ( x 1 , x 2 , … , x n )NnnКkk( х1, х2, … , ХN)(x1,x2,…,xn)(x_1, x_2, \dotsc, x_n) Вывод: vector , где - это медиана .y i ( x i , x i + 1 , … , x i + k - 1 )( у1, у2, ... , уn - k + 1)(y1,y2,…,yn−k+1)(y_1, y_2, \dotsc, y_{n-k+1})Yяyiy_i( хя,...
Вопрос: Какова самая известная нижняя граница размера формулы для явной функции в AC 0 ? Существует ли явная функция с нижней границей Ω(n2)Ω(n2)\Omega(n^2) ? Задний план: Как и большинство нижних границ, трудно найти нижние границы размера формулы. Меня интересуют нижние границы размера формулы...
Ясно, что любая проблема, которая разрешима в детерминированном пространстве журналов ( ), выполняется в самое большее полиномиальное время ( ). Существует множество классов сложности между и . Примеры включают , , , , , . Широко распространено мнение , что .P L P N L L o g C F L N C i S A C i A C...
Я знаю, что тривиально функция OR для переменных может быть точно представлена полиномом следующим образом: , который имеет степень .х 1 , ... , х п р ( х 1 , ... , х п ) р ( х 1 , ... , х п ) = 1 - П п я = 1 ( 1 - х я ) пNnnИкс1, … , ХNx1,…,xnx_1,\ldots, x_nр ( х1, … ,...
Многочлен является монотонной проекцией многочлена если = poly , и существует присваивание , что . Таким образом, можно заменить каждую переменную из на переменную или константу или так, чтобы полученный многочлен совпадал с . е(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n)m ( n ) π : { y 1 , … , y m } → { x...
Помимо (детерминированной) сложности связи отношения , другой основной мерой для объема необходимой связи является номер раздела протокола . Связь между этими двумя показателями известна до постоянного фактора. Монография Кушилевица и Нисана (1997) даетRc c ( R )сс(р)cc(R)ррR p p ( R )пп(р)pp(R) c...
Исходя из предыдущего вопроса , Каковы наилучшие текущие нижние границы пространства для SAT? С нижней границей пробела здесь я имею в виду количество ячеек рабочей ленты, используемых машиной Тьюринга, которая использует двоичный алфавит рабочей ленты. Постоянный аддитивный член неизбежен,...
Точная формулировка названия принадлежит Ананду Кулькарни (который предложил создать этот сайт). Этот вопрос был задан в качестве примера вопроса, но мне безумно любопытно. Я очень мало знаю об алгебраической геометрии, и на самом деле у меня есть только беглое понимание студентами препятствий,...
В свете недавней пропасти на глубине 3 результата (который, среди прочего, дает глубины 3 арифметическая схема дляп×попределителя надС), у меня следующие вопросы: Григорьев и Карпиньскидоказалв2Ом(п)нижняя граница для любой глубины-3 арифметической схемы вычислительной Определительп×пматрицы над...