What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable? Definitions:

positive CNF is a conjunctive normal form formula, where all literals are positive, i.e. the unary connective &not; does not exist in the formula.

negative CNF is a conjunctive normal form formula, where all literals are negative, i.e. the unary connective &not; appears next to each literal.

My question is:

Given a CNF, which is a conjunction of positive CNF and negative CNF, what is the complexity of the problem to determine that this special case of CNF is satisfiable?

Does exist polynomial time and space algorithm to solve this problem? 

EDIT: Another name for "positive CNF" is "fact CNF", where all clauses are fact and another name for "negative CNF" is "goal CNF", where all clauses are goal.

... clause with no negative literals is sometimes called a fact

... clause without a positive literal is sometimes called a goal clause

Quoted from: this wikipedia documentation
Given a CNF, which is a conjunction of positive CNF and negative CNF, what is the complexity of the problem to determine that this special case of CNF is satisfiable?


The problem is provably NP-complete by reduction from CNF satisfiability.

Each negative literal $\lnot{x}$ in a CNF SAT instance can be converted to a positive literal by replacing all occurrences of it with a new variable $z$ plus the following two CNF clauses: $x \lor z$ and $\lnot{x} \lor \lnot{z}$.  The clauses force $z$ to act as the same constraint as $\lnot{x}$.  Once all the original negated literals have been replaced, you are left with clauses that contain either all positive or all negative literals.  Since any CNF SAT instance can be reduced to this form and since CNF SAT is NP-complete and since your problem is trivially in NP, your problem must be NP-complete.