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. I prove that CLIQ$_{2}$ can't be solved in polynomial time by a deterministic TM, which infers $\mathbf{P}\neq \mathbf{NP}$. This proof upgrades the well-known proof of polynomial unsolvability of the partial result with respect to analogous monotone problem CLIQUE (abbr.: CLIQ). However, problem CLIQ$_{2}$ is not monotone and appears more complex than just iterated CLIQ, as the required subgraphs are mutually dependent (cf. Remark 27 in the text).
翻译：考虑以下NP- 问题 DOUBle CLIQUE (abr.: CLIQ$ @%2}$): 以一个自然数 $>2 美元和一个固定图形的双不连接子集决定每个子集是否包含一美元。 我证明, CLIQ$ @%2}$无法在多元时间内通过一个确定式TM解决,该确定式TM将 $\ mathbf{P ⁇ neq\mathb{NP}$。 这个证据提升了在类似一元问题CLIQUE(abr.: CLIQ)下已知的部分结果不可多解性证据(br.: CLIQ) 。 然而, CLIQ$%2} 美元的问题不是单一的,而且看起来比它本身的CLIQ更复杂,因为所需要的子集是相互依存的(参见文本中的remark 27)。
相关内容
微信扫码咨询专知VIP会员