Я хотел бы попросить предложения для хороших текстов, которые вводят сложность схемы. Любые ссылки на последние достижения и открытые проблемы в этой области также будут...
В сложности схемы у нас есть разделения между степенями различных моделей схемы. В сложности доказательства мы имеем разделения между степенями различных систем доказательства. Но в алгоритмическом у нас все еще есть только несколько разделений между степенями алгоритмических парадигм . Мои вопросы...
Информационная сложность была очень полезным инструментом в сложности коммуникации, в основном используемой для снижения сложности коммуникации в распределенных задачах. Есть ли аналог сложности информации для сложности запросов? Существует много параллелей между сложностью запросов и сложностью...
Или, другими словами, у нас есть это для каждого языка и , или ?B A ≤ p B B ≤ p AAAAВВBA ≤пВA≤пВA \leq_p BB ≤пAВ≤пAB \leq_p
Читая статью « Аппликативная теория для FPH », вы можете встретить следующий отрывок: Рассматривая теории, которые характеризуют классы вычислительной сложности, существует три разных подхода: в одном функции, которые могут быть определены в рамках теории, «автоматически» находятся в определенном...
У меня есть многогранник определенный как .PPP{x:Ax≤b,x≥0}{x:Ax≤b,x≥0}\{ x : Ax \leq b, x \geq 0\} Вопрос: Учитывая вершину из P , есть ли алгоритм полиномиального времени для равномерной выборки из соседей v в графе P ? (Многочлен в измерении, число уравнений и представление б . Я могу...
Как всем известно, знаменитая книга Гэри и Джонсона (и многие другие) дает превосходный справочник по технике редукции в классической обстановке. Существуют ли какие-либо обзоры или книги на тему техники редукции в параметризованном алгоритме, скажем, редукция...
Каждая монотонная арифметическая схема , то есть -цепь, вычисляет некоторый многомерный многочлен с неотрицательными целыми коэффициентами. Учитывая полином , схема{+,×}{+,×}\{+,\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) вычисляет если...
Когда нам дается древовидная декомпозиция графа с шириной w , есть несколько способов сделать его «красивым». В частности, известно, что его можно преобразовать в разложение дерева, где дерево является двоичным, а его высота равна O ( log n ) . Это может быть достигнуто при сохранении ширины...
Этот вопрос касается логики высказываний, и все случаи «разрешения» следует понимать как «предложенные решения». Этот вопрос является чем-то чрезвычайно основным, но это беспокоило меня некоторое время. Я вижу, как люди утверждают, что решение по предложению завершено, но я также вижу, что люди...
Существует ли линейный алгоритм временного перемешивания на месте? Это алгоритм, который способны выполнить некоторые особенно ловкие руки: равномерно разделить входной массив четного размера, а затем чередовать элементы двух половинок. У Mathworld есть краткая страница о риффл-тасовке . В...
Учитывая матрицу m×nm×nm \times n (при условии, что m≥nm≥nm \ge n ), каков самый быстрый алгоритм для вычисления его ранга и базиса столбцов? Я знаю, что это может быть решено с помощью линейного пересечения матроидов, что подразумевает детерминистический алгоритм времени...
Что произойдет, если мы определим P P A DP P A D{\bf PPAD} таким образом, чтобы вместо схемы времени Тьюринга / машины полисайта схема Тьюринга пространства журналов или схема A C 0A C0{\bf AC^0} кодировали проблему? В последнее время оказалось важным дать более быстрые алгоритмы для обеспечения...
Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...
Фон Формула однократного чтения для набора элементов (также называемая базисом) - это формула, в которой каждая входная переменная появляется один раз. Формулы однократного чтения обычно изучаются на основе де Моргана (которая имеет 2-битные логические элементы И и ИЛИ, и 1-битный вентиль НЕ) и...
Проблема #SAT является канонической # P-полной проблемой. Это скорее функциональная проблема, чем проблема решения. При булевой формуле в пропозициональной логике спрашивается, сколько удовлетворяющих заданий имеет. Каковы лучшие нижние границы на...
Учитывая два CNF, если они имеют одинаковое количество назначений, чтобы сделать их правдой, ответьте «Да», в противном случае ответьте «Нет». Легко увидеть, что это в P#PP#PP^{\#P} , поскольку, если мы знаем точное число решений этих двух CNF, мы просто собираем их и отвечаем «Да» или «Нет». В чем...
В своей статье « Приблизительные расстояния» оракулы Торупа и Цвика показали, что для любого взвешенного неориентированного графа можно построить структуру данных размера которая может возвращать ( 2 k - 1 ) -приближенный расстояние между любой парой вершин в графе.O ( к н1 + 1 / к)О(КN1+1/К)O(k...
Известны ли результаты, которые исключают существование «слишком хороших, чтобы быть правдивыми» структур данных? Например: можно ли добавить функциональность и J o i n в структуру данных ведения заказа (см. Dietz and Sleator STOC '87 ) и при этом получить O ( 1 ) временных операций?Sp l i...
Результат 1: Теорема Линиала-Мансура-Нисана говорит о том, что вес Фурье функций, вычисленных по схемам сосредоточен на подмножествах малого размера с высокой вероятностью.AC0AC0\mathsf{AC}^0 Результат 2: вес Фурье у сконцентрирован на коэффициенте степени n .PARITYPARITY\mathsf{PARITY}nnn Вопрос:...