Review of 'Note for the P versus NP Problem'

The article starts with a succinct introduction to the concepts of P, NP and NP-completeness basic to computational complexity theory. These necessary definitions, and those appearing later on in the text, are terse, to-the-point and elegantly intuitive and can be understood by anyone regardless of their level of expertise. The examples are equally informative, although the explanation of the logical proposition underlying the definition of K-closure in page 2 could perhaps benefit from a clearer wording, e.g. removing the "necessarily" from its last sentence to make it clear that this is the XOR connective. The example given for a 2CNF could also benefit from a replacement of one of the literals in its first clause, because said clause is a tautology. Definition 2, introducting the MWX2SAT problem for n-variable 2CNF formulae, makes use of the XOR operator but this is not defined in the text. None of these minor issues, however, hamper the exposition.

The paradigmatic and nuclear role NP-complete problems occupy within the NP complexity class is crucial to what comes next. Firstly, Lemma 1 establishes that a k-closure problem can be both translated into an equivalent MW2SAT problem, and characterized as NP-complete in its own right. Theorem 1 then proves that MW2SAT also belongs to the P class; this is done by equating this problem to another well known graph-related P problem (this time for undirected graphs), namely that of finding vertex sets of size at most k that are both vertex covers and independent sets.

The strategy behind the choice of analogous problems, both in Lemma 1 and in Theorem 1, is both inventive and ambitious, particularly given their simplicity, and its implications are potentially groundbreaking.

I therefore extend my recommendation for publication.