A note on the monotone complexity of 2-REF

Sharpening an argument in [2], we show that the problem of recognizing refutable propositional logic formulas in conjunctive normal form with two disjuncts is monotonic p-projection equivalent to the problem st \Gamma DCON of directed connectivity between two distinguished vertices s; t of a directed graph. It follows by [4] that the monotonic depth of bounded fan-in boolean circuits for 2 \Gamma REF is \Theta(log 2 (n)). Introduction Let k-sat [resp. k-ref] denote the set of satisfiable [resp. refutable 1 ] propositional formulas in conjunctive normal form. It has long been known that 3-sat is NP - complete and hence that 3-ref is co \Gamma NP -complete (S.A. Cook), while 2-ref is in NL hence computable in polynomial time. S.A. Cook and M. Luby gave a parallel algorithm (in NC 2 ) for the problem of testing whether a 2-cnf formula is satisfiable and if so yields a satisfying assignment. Appropriately formulated, 2-ref is a monotone problem; e.g. (x y) (x ¯ y) (¯x y) (¯x ..