cs.CC
On P Versus NP. 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).