Исследование вычислительной сложности задач по нескольким параметрам.
Известно, что некоторые проблемы неразрешимы, но, тем не менее, можно добиться определенного прогресса в их решении. Например, проблема остановки неразрешима, но можно добиться практического прогресса в создании инструментов для обнаружения потенциальных бесконечных циклов в вашем коде. Проблемы с...
Меня интересует параметризованная сложность того, что я буду называть проблемой d-мерного ударного множества: с учетом пространства диапазона (т. Е. Системы множеств / гиперграфа) S = (X, R) с VC-размерностью не более d и натуральное число k, содержит ли X подмножество размера k, которое попадает в...
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Теперь определим множества всех входов со сложностью Колмогорова и определим последовательность Здесь - средняя последовательность времени...
В параметризованной сложности, . Предполагается, что каждое из условий является правильным.⊆ W [ 2 ] ⊆ … ⊆ W [ P ]FPT⊆W[1]FPT⊆W[1]\mathsf{FPT} \subseteq \mathsf{W}[1] ⊆W[2]⊆W[2]\subseteq \mathsf{W}[2] ⊆…⊆W[P]⊆…⊆W[P]\subseteq \ldots \subseteq \mathsf{W}[P] Если то .P = W [ P...
Я хотел бы узнать о параметризованной сложности (как на алгоритмической стороне, так и на жесткости). Какие книги / конспекты лекций я могу прочитать на эту...
Treewidth играет важную роль в алгоритмах FPT, отчасти потому, что многие проблемы FPT параметризуются с помощью treewidth. Связанное, более ограниченное понятие - это пропускная способность. Если граф имеет ширину пути , он также имеет ширину дерева не более k , в то время как в обратном...
Пусть 0≤p≤10≤p≤10\le p\le 1 и рассмотрим решение задачи CLIQUE Ввод: целое числоpp_p sss , граф GGG с ttt вершинами и края Вопрос: действительно содержит клику по крайней мере вершинами?⌈p(t2)⌉⌈p(t2)⌉\lceil p\binom{t}{2} \rceil GGGsss Экземпляр CLIQUE содержит пропорцию от всех возможных ребер....
Что если что-либо известно о параметризованной сложности вычисления числа пересечений графа (наименьшее число кликов, необходимых для охвата всех его ребер)? Давно известно, что он является NP-полным, и это, очевидно, FPT, потому что у него есть ядро: если вы можете покрыть граф кликами, то...
Для заданного ненаправленного графа из вершин, какова наилучшая известная оценка времени выполнения для нахождения подграфа, который является k × k -бикликом? Существуют ли более быстрые параметризованные алгоритмы, чем алгоритм времени для "угадывания" одной стороны биклика и проверки, есть ли...
Как всем известно, знаменитая книга Гэри и Джонсона (и многие другие) дает превосходный справочник по технике редукции в классической обстановке. Существуют ли какие-либо обзоры или книги на тему техники редукции в параметризованном алгоритме, скажем, редукция...
Когда нам дается древовидная декомпозиция графа с шириной w , есть несколько способов сделать его «красивым». В частности, известно, что его можно преобразовать в разложение дерева, где дерево является двоичным, а его высота равна O ( log n ) . Это может быть достигнуто при сохранении ширины...
Учитывая график, , я хочу , чтобы найти оптимальный г -domination для G . То есть, я хочу подмножество S из V таким образом, что все вершины в G находятся на расстоянии не более чем г от некоторой вершины в S , при сведении к минимуму размера S .G=(V,E)G=(V,E)G = (V, E)rrrGGGSSSVVVGGGrrrSSSSSS Из...
-hierarchy представляет собой иерархию классов полностью в параметризованном сложности, см Сложности Зоопарк определений. Альтернативное определение определяет используя взвешенную определимость для логики первого порядка, см. Учебник Флума и Гроэ...
Мотивация: соавтор редактирует рукопись, и я хотел бы увидеть четкое резюме изменений. Все инструменты, подобные "diff", как правило, бесполезны, если вы одновременно перемещаете текст (например, реорганизуете структуру) и делаете локальные правки. Неужели так сложно понять это правильно?...
Treewidth и pathwidth являются популярными параметрами, измеряющими близость графа к дереву или пути, соответственно. В самом деле, кажется, что древовидная ширина настолько популярна, что во многих статьях, книгах и конспектах лекций, которые (даже очень осторожно) знакомят с алгоритмическими...
Покрытие Vertex может быть легко уменьшено до Независимого набора и наоборот. Однако в контексте параметризованной сложности Независимый набор сложнее, чем Vertex Cover. Ядро с вершин существует для Vertex Cover, но независимое множество W 1 жестких.2k2k2k Как меняется характер Независимого...
Вес |x||x||x|двоичной строки x∈{0,1}nx∈{0,1}nx\in\{0,1\}^n - количество единиц в строке. Что произойдет, если мы заинтересованы в вычислении монотонной функции на входах с несколькими из них? Мы знаем, что решить, имеет ли граф клик, сложно для монотонных цепей (см., Среди прочего, Alon Boppana,...
Пусть - формула 2CNF, а k - неотрицательное целое число. В этой статье доказано, что проблема принятия решения о том, можно ли удалить не более k предложений, чтобы сделать φ выполнимой, задается с фиксированным параметром, где k - параметр. Мой вопрос заключается в том, есть ли какие-либо работы,...
Пусть и обозначим через множество всех графов, которые могут быть вложены в поверхность рода , что все вершины расположены на внешней грани . Например, - это множество внешнепланарных графов. Может ли ширина графов в ограничена сверху некоторой функцией от ?G k k G 0 G k...
В параметризованной сложности люди используют сокращение с фиксированным параметром (FPT), чтобы доказать W [t] -твердость. Теоретически FPT-редукция не является редукцией за полиномиальное время, поскольку она может экспоненциально выполняться по параметру k. Но на практике все сокращения FPT,...