Parameterized Proof Complexity
Parameterized Proof Complexity
复制标题
参数化证明复杂性
DOI：
10.1007/s00037-010-0001-1
复制
发表时间：
2011
影响因子：
1.4
通讯作者：
Dantchev S
中科院分区：
文献类型：
--
作者：
Dantchev S
我们提出了一个证据理论的方法来获得证据，某些参数化的问题是不固定参数听话。我们认为证明，一个给定的命题公式不能满足的真理分配，设置在mostkvariables为真，kingkas的参数（我们称这样的公式参数化矛盾）。我们可以通过证明不存在参数化矛盾的fpt有界参数化证明系统来分离参数化复杂性类FPT和W[SAT]，即，没有一个证明系统能证明sizef（k）nO（1），其中ref是一个可计算函数，n表示命题公式的大小。通过第一步，我们介绍了系统的参数树型决议，并表明，这个系统是不是FPT有界的。事实上，我们给出了一个一般性的结果，最短的树状分辨率证明的参数化矛盾，统一编码的一阶原则的大小宇宙。我们建立了一个二分法定理，将Riis的复杂性缺口定理的指数情况分成两个子情况，一个允许sizef（k）nO（1）的证明，另一个不允许。我们还讨论了如何参数化的矛盾集可能被嵌入到一组（普通）的矛盾，通过添加新的公理。当嵌入到一般（DAG类）的决议，我们证明了鸽子洞的原则有一个大小为2kn2的证明。这与树状解析的情况形成对比，在树状解析中，嵌入的鸽子洞原理福尔斯落入我们二分法的“非FPT”类别。
We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at mostkvariables totrue, consideringkas the parameter (we call such a formula a parameterized contradiction). One could separate the parameterized complexity classes FPT and W[SAT] by showing that there is no fpt-bounded parameterized proof system for parameterized contradictions, i.e., that there is no proof system that admits proofs of sizef(k)nO(1)wherefis a computable function andnrepresents the size of the propositional formula. By way of a first step, we introduce the system of parameterized tree-like resolution and show that this system is not fpt-bounded. Indeed, we give a general result on the size of shortest tree-like resolution proofs of parameterized contradictions that uniformly encode first-order principles over a universe of sizen. We establish a dichotomy theorem that splits the exponential case of Riis’s complexity gap theorem into two subcases, one that admits proofs of sizef(k)nO(1)and one that does not. We also discuss how the set of parameterized contradictions may be embedded into the set of (ordinary) contradictions by the addition of new axioms. When embedded into general (DAG-like) resolution, we demonstrate that the pigeonhole principle has a proof of size 2kn2. This contrasts with the case of tree-like resolution where the embedded pigeonhole principle falls into the “non-FPT” category of our dichotomy.
简单就是美：改进顶点覆盖的上限
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
Jianer Chen;Iyad A. Kanj y;Ge Xia
通讯作者：
Ge Xia
证明作为游戏
DOI：
10.1080/00029890.2000.12005233
发表时间：
2000
期刊：
The American Mathematical Monthly
影响因子：
--
作者：
P. Pudlák
通讯作者：
P. Pudlák
树解析的复杂性差距
影响因子：
1.4
作者：
Søren Riis
通讯作者：
Søren Riis