Гомоморфизм из графаG=(V,E)G=(V,E)G = (V, E) на график G′=(V′,E′)G′=(V′,E′)G' = (V', E') это отображение fff от VVV в V′V′V' такой, что если xxx а также yyy смежны в EEE тогда f(x)f(x)f(x) а также f(y)f(y)f(y) смежны в E′E′E', Эндоморфизм графаGGG является гомоморфизмом из GGGк себе; это без...
Каков наилучший результат для числа затворов в схеме, умножающей два n-разрядных целых числа? Очевидный метод генерирует θ (N2)θ(N2)\theta(n^2)ворота. Есть лучшие подходы сθ(nlognloglogn)θ(nlognloglogn)\theta(n\log n \log\log n) а также θ(nlogn2log∗(n))θ(nlogn2log∗(n))\theta(n\log...
Скажем, у нас есть булева функция f:{−1,1}n→{−1,1}f:{−1,1}n→{−1,1}f:\{-1,1\}^n\rightarrow \{-1,1\} и мы применяем δδ\deltaслучайное ограничение на fff, Кроме того, скажем, что дерево решенийTTT это вычисляет fff сжимается до размера O(1)O(1)O(1)в результате случайного ограничения. Означает ли это,...
Прошу прощения, это немного "мягкий" вопрос. Теория информации не имеет понятия вычислительной сложности. Например, экземпляр SAT или экземпляр SAT плюс бит, указывающий на выполнимость, несут одинаковое количество информации. Есть ли способ формализовать понятие «полиномиально узнаваемый»? Такая...
Что известно о сложности решения системы линейных уравнений над некоторым конечным полем? Я знаю, что существуетO (N3)O(n3)O(n^3)алгоритм (Гаусса), который вычисляет решение и что для разреженных систем есть еще лучшие алгоритмы. Однако мне было интересно, была ли какая-то теоретическая...
Какой самый быстрый из известных алгоритмов изоморфизма неориентированных
Я изучаю гипотезу об уникальных играх и известное сведение к Max-Cut из Khot et al. Из их статьи и из других источников в Интернете большинство авторов используют (что для меня является) неявную эквивалентность между сокращением MAX-CUT и созданием конкретных тестов для длинных кодов. Из-за моей...
Давайте исправим кодировку машин Тьюринга и универсальной машины Тьюринга U, которая на входе (T, x) выводит все выходные данные T на входе x (возможно, оба работают вечно). Определим колмогоровскую сложность x, K (x) как длину самой короткой программы p, такой, что U (p) = x. Существует ли N...
Экземпляр: неориентированный графGGGс двумя выделенными вершинами и целым числом .s≠ts≠ts\neq tk≥0k≥0k\geq 0 Вопрос: существует ли путь в , такой, что путь пересекает не болееs−ts−ts-tGGGkkkтреугольники? (Для этой задачи говорят, что путь пересекает треугольник, если путь содержит хотя бы одно...
Позволять G = ( V, E)гзнак равно(В,Е)G=(V,E)быть графом Набор вершинИкс⊆ VИкс⊆ВX\subseteq Vназывается критическим, еслиИкс≠ ∅Икс≠∅X\neq\emptyset и нет вершины в В∖ XВ∖ИксV\setminus X смежна ровно с одной вершиной в ИксИксX, Проблема состоит в том, чтобы найти множество вершинS⊆ VS⊆ВS\subseteq V...
Если мы рассмотрим только проблемы в P, есть ли какие-то большие промежутки между самым быстрым из известных алгоритмов слово-RAM и самым быстрым из известных алгоритмов машины Тьюринга для конкретных задач? Мне особенно интересно, есть ли большие пробелы для естественных проблем, представляющих...
Стандартная проблема 1-в-3 SAT (или XSAT или X3SAT): Экземпляр : формула CNF с каждым предложением, содержащим ровно 3 литерала. Вопрос : есть ли удовлетворительная установка присваивания, точно равная 1 литералу на предложение, верно? Проблема является NP-полной и остается сложной, даже если...
Это продолжение недетерминированного ускорения детерминированных вычислений . Возможно ли, что недетерминизм (или, в более общем смысле, чередование) позволил бы общее квадратичное ускорение детерминированных вычислений? Или есть какие-то известные неправдоподобные последствия для чего-то вроде...
Позволять ΣΣ\Sigma быть алфавитом размера 222и рассмотрим минимальные DFA, размер которых ограничен не более мmm, Позволятье( м )f(m)f(m) обозначим количество различных таких минимальных ДФА. Можем ли мы найти формулу замкнутой формы для е( м )f(m)f(m)? Учитывая, что для | Σ | =2|Σ|=2|\Sigma|=2...
Для фиксированного языка LLL на каком-то алфавите AAA, давайте рассмотрим следующую проблему, которую я называю LLL-Интерлевинг : Вход: два слова u,v∈A∗u,v∈A∗u, v \in A^* Вывод: существует ли там перемежения изuuu а также vvv который в LLL, Здесь чередование двух словuuu а также vvv это слово www...
Квазиполиномиальное время, или сокращенно QP, является классом сложности на детерминированной машине Тьюринга. Вот точное определение: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp В то время как βP является классом сложности ограниченного недетерминизма. Вот точное определение:...
Есть ли какое-нибудь известное вычислимое трансцендентное число такое, что его NnnЭта цифра вычисляется за полиномиальное время, но не в O ( n
Что такое метод приближений Разборова? Может ли кто-нибудь дать обзор высокого уровня и интуицию, стоящую за
После новых и новых успехов нейронных сетей в игре в настольные игры, мы чувствуем, что следующая наша цель может быть чем-то более полезным, чем победа над людьми в Starcraft. Точнее, я задавался вопросом, Можно ли обучить нейронные сети для решения классических алгоритмических задач? Здесь я имею...
Каковы наиболее известные асимптотические верхние оценки размеров вероятностно проверяемых доказательств? В идеале я ищу современное исследование по этому широкому вопросу, но если его нет, меня особенно интересует неприемлемость 3-SAT. Пусть 7/8 + ε-3-SAT будет 3-SAT с обещанием, что если 7/8 + ε...