Естественные полные проблемы на более высоких уровнях

13

-hierarchy представляет собой иерархию классов полностью в параметризованном сложности, см Сложности Зоопарк определений. Альтернативное определение определяет используя взвешенную определимость для логики первого порядка, см. Учебник Флума и Гроэ .WW[t]W[t]Πt

Для низших классов и W [ 2 ] известно много естественных полных задач, например, Клика и Независимый Набор завершены для W [ 1 ] , а Доминирующий Набор и Набор Ударов завершены для W [ 2 ] , где каждая из этих задач определяется как соответствующая известная N P -полная задача с размером требуемого решения, установленного в качестве параметра. W[1]W[2]W[1]W[2]NP

Существуют ли известные естественные полные проблемы для классов выше в иерархии, в частности для W [ 3 ] и W [ 4 ] ?WW[3]W[4]

Ян Йоханнсен
источник
2
В этой статье доказано, что p-HYPERGRAPH- (NON) -DOMINATING-SET является W [3] -полным при fpt-сокращениях ... но я думаю, что это трудно считать "естественным" :-) :-)
Марцио де Биаси,
2
Ну, по крайней мере, это выглядит более естественно, чем определяющие проблемы, не так ли?
Ян Йоханнсен

Ответы:

11

Из комментария выше:

ГИПЕРГРАФ- (НЕ) -DOMINATING-SETpявляется W [3] -полным при fpt-сокращениях:

Гиперграф состоит из множества V вершин и множества Х гиперреберов. Каждый гиперребро как подмножество V . В 3-гиперграфе все ребра имеют размер 3. Если H = ( V , E ) является 3-гиперграфом, то каждый a V индуцирует граф H a = ( V a , E a ), определяемый как:H=(V,E)VEVH=(V,E)aVHa=(Va,Ea)

и E a = { { u , v } { a , u , v } E }Va={vVva and there is eE with a,ve}Ea={{u,v}{a,u,v}E}

Вход : 3-гиперграф , множество M V и k 1 . Параметр : к . Проблема : Решите, существует ли множество D V мощности k такое, что:H=(V,E)MVk1
k
DVk

  • если , то D является доминирующим множеством H a ,aMDHa
  • если , то D не является доминирующим множеством H a .aMDHa

см. Йиджи Чен, Йорг Флум и Мартин Гроэ. Анализ W * -иерархии. Журнал символической логики, Vol. 72, № 2 (Jun., 2007), с. 513-534

Марцио де Биаси
источник
13

Я полагаю, что название этой статьи не требует пояснений и отвечает на ваш вопрос: Об охвате продукта в трехуровневых моделях цепочки поставок: естественные полные проблемы для W [3] и W [4]

Исин Цао
источник
Определение проблем в этой статье не так легко прочитать, потому что авторы не четко различают модель и то, что моделируется. Но, насколько я понимаю, они - просто замаскированные взвешенные проблемы SAT. Они могут быть полезны для предметной области, но я сомневаюсь, что их удобнее сокращать.
Ян Йоханнсен
Я частично согласен с вами в том, что эти проблемы не так естественны, как покрытие вершины / клика / доминирующее множество и т. Д. Но, поскольку все больше и больше проблем изучается, но новых кандидатов не возникает, нам, возможно, придется обратиться к этим субестественным проблемам.
Исинь Цао
Я не говорю, что эти проблемы не являются естественными. Я хочу сказать, что они не сильно отличаются от задач взвешенного SAT для схем глубины три. Насколько я понимаю, это более или менее одна и та же проблема, написанная в другой терминологии.
Ян Йоханнсен