{"id":"arxiv/2606.05512","url":"https://arxiv.org/abs/2606.05512","tags":["cs.CC","math.LO"],"score":0,"title":"Polynomial-time satisfiability for a special case of Positive$\\wedge$Negative","domain":"cs.CC","source":"arxiv","authors":["Marcel Wild"],"reviews":0,"subject":"cs.CC","summary":"A Boolean function in CNF format is of type Positive$\\wedge$Negative} if each clause C is either positive (i.e. all literals of C are positive) or negative (i.e. all literals of C are negative). As is well known, deciding the satisfiability of such CNFs is NP-complete. We say that a CNF is of type DisjointPositive if its clauses are positive and mutually disjoint. Dually define DisjointNegative. It is shown that the satisfiability of CNFs of type DisjointPositive$\\wedge$DisjointNegative can be decided in quadratic time. Moreover, the modelset can be output in polynomial total time. This is…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-03","reactions":{}}