Известны ли субэкспоненциальные алгоритмы для PLANAR SAT?

Некоторые NP-сложные задачи, которые являются экспоненциальными на общих графах, являются субэкспоненциальными на плоских графах, потому что ширина дерева не более и они экспоненциальны в ширине дерева. $4.9 \sqrt{|V(G)|}$

В основном меня интересует, существуют ли субэкспоненциальные алгоритмы для PLANAR SAT, которые являются NP-полными.

Пусть - формула CNF для переменных а предложение - . $\phi$ $x_i$ $i$ $c_i$

Частота график р. 5 функции находится на вершинах и ребрах если или . $G$ $\phi$ $V(G)=\{x_i\} \cup \{c_i\}$ $(x_i,c_i)$ $x_i \in c_i$ $\lnot x_i \in c_i$

находится в PLANAR SAT, если график заболеваемости плоский. $\phi$

Существуют ли субэкспоненциальные алгоритмы для PLANAR SAT в терминах ? $\phi$

Я не исключаю возможности уменьшения SAT до PLANAR SAT, чтобы сделать это возможным, хотя SAT все еще будет экспоненциальным, а субэкспоненциальным из-за увеличения размера. $\phi$

graph-theory sat reductions Joro
источник

В определении PLANAR SAT есть дополнительное условие: переменные должны быть связаны с циклом через них. То, что вы описали, называется PLANAR * SAT.

Домоторп

@domotorp Я думаю, что процитировал правильно, и газета утверждает, что график является двудольным Может быть, в других статьях это имя используется для чего-то другого.

Джор

Ну, вы можете применить теорему о плоском разделителе вместе с динамическим программированием и получить время выполнения

, где

- количество вершин в графе. Я полагаю, вы хотите что-то лучше?

2^{O (\sqrt{n})}

$2^{O( \sqrt{n})}$

n

$n$

Сариэль Хар-Пелед

@ SarielHar-Peled Ваш ответ будет, не нужно что-то лучше (хотя лучше, добро пожаловать). Ошибки в разных формулах могут иметь один и тот же график - отрицание литерала.

Joro

2^{o (\sqrt{n})}

$2^{o(\sqrt{n})}$

Ну, вы можете применить теорему о плоском разделителе вместе с динамическим программированием и получить время выполнения 2 O ( $2^{O(\sqrt{n})}$ $n$

Если узел предложения большой, то вы должны быть немного умнее - вам нужно угадать, назначить ли его левой или правой стороне подзадачи. Детали таких вещей, как правило, беспорядочные, а не немедленные, поэтому я не буду вдаваться в подробности. Я думаю, что оригинальные статьи Липтона и Тарьяна решили подобные проблемы, используя похожие идеи, если моя память мне не изменяет.

Сариэль Хар-Пелед
источник

k

$k$

2^{O (k)} p o l y (| ϕ |)

$2^{O(k)} poly(|\phi|)$

n

$n$

O (\sqrt{n})

$O(\sqrt{n})$

H

$H$

O (\sqrt{n})

$O(\sqrt{n})$

H

$H$

n

$n$

m

$m$

O (\sqrt{n})

$O(\sqrt{n})$

O (\sqrt{n + m})

$O(\sqrt{n+m})$

O (\sqrt{n})

$O(\sqrt{n})$

n

$n$

O (\sqrt{n})

$O(\sqrt{n})$

Это также упражнение 41 из Точных алгоритмов Woeginger's 2003 для NP-сложных задач: обзор . dx.doi.org/10.1007/3-540-36478-1_17

Саламон

Известны ли субэкспоненциальные алгоритмы для PLANAR SAT?

Ответы: