Я хотел бы узнать о параметризованной сложности (как на алгоритмической стороне, так и на жесткости). Какие книги / конспекты лекций я могу прочитать на эту...
Существует ли какой-либо текущий проект по формальной проверке теорем и доказательств теории сложности с использованием помощника по доказательствам, такого как Coq? Есть ли границы для...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Я никогда раньше не видел алгоритм с логом в знаменателе, и мне интересно, есть ли какие-нибудь действительно полезные алгоритмы с этой формой? Я понимаю много вещей, которые могут привести к умножению логарифмического коэффициента во время выполнения, например, сортировка или алгоритмы на основе...
XORification - это метод усложнения булевой функции или формулы путем замены каждой переменной на XOR k ≥ 2 различных переменных x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Мне известно об использовании этого метода для усложнения доказательства, главным образом для...
Все ли функции, чей вес Фурье сконцентрирован на множествах малого размера (или членах с низкой степенью), вычисляются по схемам
Хорошо известно, что квантовые компьютеры являются строго более мощными, чем их классические аналоги, с точки зрения сложности запросов . Существуют ли другие модели (естественные или искусственные), которые строго находятся между квантовой и классической с точки зрения сложности запросов?...
Как я могу определить количество уникальных простых путей в неориентированном графе? Либо для определенной длины, либо диапазона приемлемых длин. Напомним, что простой путь - это путь без циклов, поэтому я говорю о подсчете количества путей без...
Работать напрямую со сложностью времени или нижними границами схемы страшно. Следовательно, мы разрабатываем такие инструменты, как сложность запросов (или сложность дерева решений), чтобы справиться с нижними границами. Поскольку каждый запрос занимает по крайней мере один блок-шаг, а вычисления...
Теория категорий и абстрактная алгебра имеют дело со способом, которым функции могут быть объединены с другими функциями. Теория сложности имеет дело с тем, насколько сложно вычислить функцию. Мне странно, что я не видел, чтобы кто-нибудь совмещал эти области изучения, поскольку они кажутся такими...
Какова сложность (в стандартном целочисленном ОЗУ) вычисления стандартного дискретного преобразования Фурье вектора из nNn целых чисел? Классический алгоритм для быстрых преобразований Фурье , неуместно [1] приписываемый Кули и Тьюки, обычно описывается как выполняющийся за O(nlogn)О(NжурналN)O(n...
Была ли проделана какая-либо работа над тем, как сложность случайных экземпляров # 2-SAT зависит от плотности предложения? То есть: как изменяется сложность подсчета удовлетворяющих решений для случайно сгенерированного экземпляра 2-SAT , когда меняется плотность предложений? В частности, известны...
Предположим, что TTT - дерево постоянной степени, структура которого мы не знаем. Проблема состоит в том, чтобы вывести дерево , задавая запросы в форме: «Находится ли узел на пути от узла к узлу ?». Предположим, что на каждый запрос оракул может ответить в постоянное время. Мы знаем значение ,...
Treewidth играет важную роль в алгоритмах FPT, отчасти потому, что многие проблемы FPT параметризуются с помощью treewidth. Связанное, более ограниченное понятие - это пропускная способность. Если граф имеет ширину пути , он также имеет ширину дерева не более k , в то время как в обратном...
Я думаю, что теорема об иерархии размеров для сложности схемы может быть главным прорывом в этой области. Это интересный подход к разделению классов? Мотивация вопроса заключается в том, что мы должны сказать есть некоторая функция, которая не может быть вычислена схемами размера и может быть...
Рассмотрим язык 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 ≠ σ я...
Я пытаюсь решить конкретную проблему, и я подумал, что смогу решить ее, используя теорию автоматов. Мне интересно, какие модели автоматов имеют разрешимость за полиномиальное время? то есть если у вас есть машины вы можете проверить, эффективно ли . L ( M 1 ) ⊆ L ( M 2 )M1, M2M1,M2M_1, M_2Л ( М1) ⊆...
РЕДАКТИРОВАТЬ (22 августа 2011 г.): Я еще больше упрощаю вопрос и назначаю вознаграждение за этот вопрос. Возможно, на этот более простой вопрос будет легко ответить. Я также собираюсь зачеркнуть все части оригинального вопроса, которые больше не актуальны. (Спасибо Стасису Юкне и Райану О'Доннелу...
задира Поскольку проблема длинная, здесь есть особый случай, который отражает ее суть. Проблема: Пусть A - детриминистический алгоритм для 3-SAT. Является ли проблема полного моделирования алгоритма A (на каждом экземпляре задачи). P-Space сложно? (Точнее, есть ли основания полагать, что эта задача...
Мне сказали, что есть несколько хороших алгоритмов полиномиального времени для аппроксимации числа простых путей в ориентированном графе от заданной начальной вершины до заданной конечной вершины t . Кто-нибудь знает хорошую ссылку на эту тему?sssTTt Справочная информация: подсчет точного числа...