Было доказано, что распространение убеждений является очень мощным методом исследования вероятностных графических моделей. Однако я ничего не знаю о BP, сравнимом с методами MCMC, где у нас могут быть полностью полиномиальные схемы рандомизированной аппроксимации (FPRAS) для # P-полных задач. Может...
В другом посте cstheorySE упоминается, что PSPACE-полнота подразумевает APX-жесткость. Кто-нибудь может объяснить / поделиться ссылкой на это? Это "плотно"? (т. е. существуют ли PSPACE-полные задачи, задача оптимизации которых допускает постоянную аппроксимацию множителя за много времени?) Как...
Мне кажется, что большинство теоретиков сложности обычно верят в следующее философское правило: Если мы не можем найти эффективный алгоритм для задачи и можем свести проблему A к проблеме B , то, вероятно, эффективного алгоритма для проблемы B тоже нет.AAAAAABBBBBB Вот почему, например, когда новая...
Я хочу узнать об алгебраических алгоритмах и их сложности. В частности, меня интересует PIT. Есть ли набор лекций, книг, статей и опросов для студентов, которые читали стандартный учебник по теории, такой как книга Сипсера или учебник по сложности Арора-Барака. Набор ссылок будет включать в себя...
Я читал статью в Википедии о проблеме восьми королев. Установлено, что не существует известной формулы для точного числа решений. После некоторых поисков я нашел статью под названием «О сложности подсчета проблем полных отображений». В этой статье есть проблема, показанная не более, чем #queens,...
Мы рассматриваем DAG (ориентированные ациклические графы) с одним исходным узлом sss и одним целевым узлом ttt ; допускаются параллельные ребра, соединяющие одну и ту же пару вершин. - разрез представляет собой набор ребер, удаление уничтожает все - пути по длиннее , чем ; более короткие - пути, а...
Разборов доказал, что соответствие монотонной функции отсутствует в мП . Но можем ли мы вычислить соответствие, используя схему полиномиального размера с несколькими отрицаниями? Существует ли P / поли схема с O(nϵ)O(nϵ)O(n^\epsilon) отрицаниями, которая вычисляет совпадение? Каков компромисс между...
Рассмотрим вектор переменных и набор линейных ограничений, заданных как .x⃗ x→\vec{x}Ax⃗ ≤bAx→≤bA\vec{x}\leq b Кроме того, рассмотрим два многогранника P1P2={(f1(x⃗ ),⋯,fm(x⃗ ))∣Ax⃗ ≤b}={(g1(x⃗ ),⋯,gm(x⃗ ))∣Ax⃗ ≤b}P1={(f1(x→),⋯,fm(x→))∣Ax→≤b}P2={(g1(x→),⋯,gm(x→))∣Ax→≤b}\begin{align*}...
Постоянное время - это абсолютный нижний предел сложности времени. Можно задаться вопросом: есть ли что-нибудь нетривиальное, что можно вычислить за постоянное время? Если мы придерживаемся модели машины Тьюринга, то мало что можно сделать, поскольку ответ может зависеть только от начального...
Для любого произвольного NP-полного языка всегда ли найдется надмножество множителей, дополнение которого также бесконечно? На /cs//q/50123/42961 была запрошена тривиальная версия, в которой суперсет не должен иметь бесконечного дополнения. Для целей этого вопроса можно предположить, что . Как...
Согласно Сложности Zoo , и мы знаем, что R e g не может сосчитать, поэтому T C 0 ⊈ R e g . Однако это не говорит, если R e g ⊆ T C 0 или нет. Поскольку мы не знаем N C 1 ⊈ T C 0, мы также не знаем R e g ⊈ T C 0 .Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1}RegReграмм\mathsf{Reg}TC0E R...
В ККk -й элементарный симметричный полином SNК( х1, … , ХN)SКN(Икс1,...,ИксN)S_k^n(x_1,\ldots,x_n) является суммой всех продуктов различных переменных. Меня интересует сложность монотонной арифметической схемы этого многочлена. Простой алгоритм динамического программирования (как и рис. 1 ниже)...
Может ли недетерминизм ускорить детерминистские вычисления? Если да, то сколько? Под ускорением детерминированных вычислений недетерминизмом я подразумеваю результаты вида: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Например, что-то вроде...
Была ли проведена работа по поиску минимального числа элементарных арифметических операций, необходимых для вычисления определителя матрицы NNn на NNn для малых и фиксированных NNn ? Например, n = 5Nзнак равно5n=5...
Какова сложность следующей проблемы? Вход : гамильтонов путьв К пHHHKnКNK_n R⊆[n]2р⊆[N]2R \subseteq [n]^2 подмножество пар вершин положительное целое число kКk Запрос : существует ли сопоставление MMM такое, что для каждого (v,u)∈R(v,U)∈р(v,u) \in R , dG(v,u)≤kdграмм(v,U)≤Кd_G(v,u) \leq k ? (где...
Пусть будет функцией, которая отображает схему s- гейта C на n битов и n- битную строку x на C ( x ) . Предположим, что схемы кодируются как ациклическая последовательность назначений k : = g ( i , j ), где i , j , k - метки проводов.C i r c u i t E v a lс , нСярсUяTЕvaLs,N\mathsf{CircuitEval}_{s,...
Учитывая темы, затронутые на конференции, такие как STOC, активно ли исследователи алгоритмов или сложности используют COQ или Изабель? Если да, то как они используют это в своих исследованиях? Я предполагаю, что большинство людей не будут использовать такие инструменты, потому что доказательства...
Язык находится в если существует машина Тьюринга для пространства журналов, которая решает язык с полиномиальным количеством рекомендаций.Л / р о л уL/поLYL/poly Смотрите здесь для получения дополнительной информации: https://en.wikipedia.org/wiki/L/poly Вопрос Каковы последствия ?п⊆L / p o l...
В чем сложность определения, содержит ли интервал натуральных чисел простое число? Вариант решета Эратосфена дает алгоритм, где L является длина интервала и ~ Шкуры поли-логарифмические факторы в исходной точке интервала; мы можем сделать лучше (с точки зрения L только)?O~(L)O~(L)\tilde...
Благодаря Immerman и Szelepcsényi известно, что если f = Ω ( log ) (даже для непространственных конструктивных функций).NSPACE(f)=coNSPACE(f)NSPACE(f)=coNSPACE(f){\rm NSPACE}(f)={\rm coNSPACE}(f)f=Ω(log)f=Ω(log)f=\Omega(\log) В той же статье Иммерман заявляет, что переменная иерархия пространства...