论文标题
对称地近似约束满意度问题
Approximating Constraint Satisfaction Problems Symmetrically
论文作者
论文摘要
本文研究了约束满意度问题（CSP）的最佳值在多大程度上可以通过计数（FPC）的固定点逻辑的某些句子近似。众所周知，假设$ \ mathsf {p} \ neq \ mathsf {np} $和唯一的游戏猜想，则通过求解和四舍五入特定的半决赛编程放松，给出了任何CSP的最佳多项式时间近似算法。我们证明了该算法的类似物，该算法可定义为FPC解释，该算法无需假设$ \ Mathsf {p} \ neq \ neq \ Mathsf {np} $。虽然我们无法（FPC反复）作为一个假设，但我们确实为证明这一点提供了一些部分结果。具体而言，我们提供了一种新颖的结构，该结构表明，对于所有$α> 0 $，存在一个正整数$ q = \ text {poly}（\ frac {1}α）$，因此没有FPC解释，可以提供$α$ approximation $α$ - 对尺寸$ q $ $ q $的独特游戏的应用。
This thesis investigates the extent to which the optimal value of a constraint satisfaction problem (CSP) can be approximated by some sentence of fixed point logic with counting (FPC). It is known that, assuming $\mathsf{P} \neq \mathsf{NP}$ and the Unique Games Conjecture, the best polynomial time approximation algorithm for any CSP is given by solving and rounding a specific semidefinite programming relaxation. We prove an analogue of this result for algorithms that are definable as FPC-interpretations, which holds without the assumption that $\mathsf{P} \neq \mathsf{NP}$. While we are not able to drop (an FPC-version of) the Unique Games Conjecture as an assumption, we do present some partial results toward proving it. Specifically, we give a novel construction which shows that, for all $α> 0$, there exists a positive integer $q = \text{poly}(\frac{1}α)$ such that no there is no FPC-interpretation giving an $α$-approximation of Unique Games on a label set of size $q$.
