1

I will try to answer now my own question and would be glad about some feed back concerning the corectness. Like in the question above discussed and pointed out by Kyle Jones we can reduce arbitrary 3-SAT formulas to monotone 3-SAT formulas. For example a clause $C=(x_1\vee x_2 \vee \neg x_3)$ can be converted to $C'(x_1\vee x_2 \vee z_3)\wedge (z_3 \vee x_3) ...


Only top voted, non community-wiki answers of a minimum length are eligible