Consider a following NP-problem DOUBLE CLIQUE (abbr.: CLIQ$_{2}$): Given a natural number $k>2$ and a pair of two disjoint subgraphs of a fixed graph $G$ decide whether each subgraph in question contains a $k$-clique. We prove that CLIQ$_{2}$ can't be solved in polynomial time by a deterministic TM. Clearly this is equivalent to analogous claim related to the well-known monotone problem CLIQUE (abbr.: CLIQ), which infers $\mathbf{P}\neq \mathbf{NP}$. Our proof of polynomial unsolvability of CLIQ$_{2}$ upgrades the well-known "monotone" proof with respect to CLIQ. However note that problem CLIQ$_{2}$ is not monotone and it appears to be more complex than just iterated CLIQ, as the required subgraphs are mutually dependent (see also Remark 26 in the text).
翻译：考虑以下NP- 问题 DOUBLE CPIQUE (abr.: CLIQUE) : 给一个自然数字 $> 2$ 和固定图形的两个脱节子集 $G$ 来决定每个子集是否包含 $- collique 。 我们证明, CLIQ$ ⁇ 2} 无法通过确定性TM 在多元时间内解决 。 显然, 这相当于与众所周知的单人问题 CLIQUE (abr.: CLIQ) 有关的类似索赔(abr.: CLIQ), 指 $\ mathbf{P\ ne q\ mathbf{NP} $ 。 我们关于CLIQ$% 2} $ 的多元性不可溶性证据升级了众所周知的与 CLIQ 有关的“ monoone” 证据。 但是, 问题 CLIQ $%2} 不是单一的, 并且看来比单质的CLIQ更复杂,因为所要求的子集是相互依存的(另见)。
相关内容
微信扫码咨询专知VIP会员