Этот вопрос мотивирован вопросом MathOverflow Пэна Чжана . Валиант показал, что подсчет максимальных клик в общем графе является # P-полным, но что если мы ограничимся графами несопоставимости (т. Е. Мы хотим подсчитать максимальные антицепи в конечном множестве)? Этот вопрос кажется достаточно...
То, что я называю подсчетом, - это проблема, заключающаяся в том, чтобы найти количество решений для функции. Точнее, если задана функция f:N→{0,1}f:N→{0,1}f:N\to \{0,1\} (не обязательно черный ящик), приблизительный #{x∈N∣f(x)=1}=|f−1(1)|#{x∈N∣f(x)=1}=|f−1(1)|\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|,...
Недавно я изучал введение в голографические алгоритмы. Я столкнулся с некоторыми комбинаторными объектами, которые называются пфаффианцами. Я не очень много знаю о них на данный момент и натолкнулся на некоторые неожиданные способы их использования. Например, я узнал, что их можно использовать для...
Пусть G связный граф. Какова сложность подсчета всех связанных подграфов, если G имеет следующие типы? G является общим. Г плоская. G является двудольным. Я не забочусь о каких-либо структурах или ..., просто нужно сосчитать все связанные подграфы! Меня также интересует сложность подсчета всех...
У меня есть часть попытки доказательства . Попытка доказательства состоит в сокращении Карпа из -полной задачи 3-REGULAR VERTEX COVER к SAT.⊕P⊆NP⊕P⊆NP\oplus \mathbf{P} \subseteq \mathbf{NP}⊕P⊕P\oplus \mathbf{P}⊕⊕\oplus Учитывая кубический граф , сокращение выводит формулу CNF, имеющую оба следующих...
Дан ориентированный граф с n узлами, такими, что каждая вершина имеет ровно два исходящих ребра, и натуральное число N, закодированное в двоичном виде, две вершины s и t, Я хочу посчитать количество (не обязательно простых) путей от s до t в течение N шагов. Это # P-сложная проблема? Или вообще, в...
Автор: http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf. Если является PSPACE-полный язык, Р = N P A .AAAпA= NпAPA=NPAP^{A}=NP^{A} Если является детерминированным оракулом полиномиального времени, P B ≠ N P B (при условии, что P ≠ N P ).ВBBпВ≠ NпВPB≠NPBP^{B}\ne NP^{B}п≠ NпP≠NPP\ne NP -...
Для полиномиальной задачи локального поиска мы знаем, что должно существовать хотя бы одно решение (локальный оптимум). Тем не менее, может существовать гораздо больше решений, насколько сложно сосчитать количество решений для PLS-полной задачи? Меня особенно интересует проблема решения: есть ли у...
В противоположной формуле CNF с двойным чтением каждая переменная появляется дважды, один раз положительный и один раз отрицательный. Меня интересует проблема , которая заключается в вычислении четности числа удовлетворяющих назначений противоположной формуле CNF с .⊕...
Я предполагаю, что это назвали бы # P-Space, но я нашел только одну статью, смутно упоминающую это. Как насчет подсчета версий EXP-TIME-Complete, NEXP-Complete, а также проблем EXP-SPACE-Complete? Есть ли какие-либо предыдущие работы, которые можно привести в отношении этого или любого типа...
Что известно о фазовом переходе в задачах # P-Complete? В частности, существует ли другой фазовый переход для # DNF-k-SAT и # CNF-k-SAT? Обновление: Как мы знаем, в Random k-SAT есть фазовый переход, где решение проблемы переходит от простого к сложному и снова к легкому. Я хотел бы знать,...
Я заинтересован в следующей проблеме. В качестве входных данных нам дается «целевая перестановка» , а также упорядоченный список индексов i 1 , … , i m ∈ [ n - 1 ] . Затем, начиная со списка L = ( 1 , 2 , … , n ) (т. Е. Перестановки тождеств), на каждом временном шаге t ∈ [ m ] мы меняем элемент i...
Этот вопрос возник у меня в голове после прочтения вклада Андраса Саламона и Колина Маккуиллана в мой предыдущий вопрос « Подсчет решений формул Monotone-2CNF» . РЕДАКТИРОВАТЬ 30- го марта 2011 г. Добавлен вопрос № 2. РЕДАКТИРОВАТЬ 29- го октября 2010 г. Вопрос перефразирован после предложения...
КРАТКИЙ ВОПРОС: Является ли MAJ-3CNF PP-полной проблемой при сокращении многие-один? ДОПОЛНИТЕЛЬНАЯ ВЕРСИЯ: Общеизвестно, что MAJSAT (решающий, удовлетворяет ли большинство назначений пропозиционального предложения) PP-завершено при сокращениях много-один, а #SAT # P-завершено при сокращениях....
Я просматривал оригинальную статью Les Valiant, и мне было тяжело с предложением 4.3 на странице 10 статьи. Я не могу понять, почему это так, что если существует генератор с определенными значениями для с базисом { ( a 1 , b 1 ) … ( a r , b r ) } , то существует некоторый генератор с таким же v a l...
Рассмотрим классическую # P-полную задачу # 3SAT, т. Е. Посчитаем количество оценок, чтобы сделать 3CNF с переменными выполнимыми. Меня интересует аддитивная аппроксимируемость. Ясно, что существует тривиальный алгоритм для достижения -ошибки, но если , возможно ли иметь эффективный алгоритм...
Гомоморфизм из графа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к себе; это без...
Рассмотрим формулу Monotone 3CNF, имеющую оба следующих дополнительных ограничения: Каждая переменная появляется в точности 222 статьи. Учитывая любой 222 пункты, они разделяют не более 111 переменная. Я хотел бы знать, насколько сложно рассчитывать удовлетворяющие задания такой формулы. Обновление...
Позволять G=(V,E)гзнак равно(В,Е)G = ( V, E )быть графом Позволятьk≤|V|К≤|В|k \leq |V|быть целым числом ПозволятьOkОКO_k быть количеством краевых индуцированных подграфов GгG имеющий kКkвершины и нечетное количество ребер. ПозволятьEkЕКE_k быть количеством краевых индуцированных подграфов GгG...
В предыдущем вопросе « Параметризованный алгоритм поиска бикликов» я поинтересовался, существуют ли быстрые параметризованные алгоритмы для нахождения -биклика в графе вершин, и узнал, что он открыт, если он равен FPT относительно . То же самое верно и для подсчета в -bicliques, или известно , что...