Marco Benini

An exact formula for satisfiability

Let be an instance of SAT. As in a previous post, let denote the i-th clause. Moreover, let . We know that . Evidently, is the set of assignments falsifying … Continue reading

April 1, 2011 · 1 Comment

A quick satisfiability check

As it is well-known, Boolean Satisfiability, SAT for short, is NP-complete. Suppose is a formula where is a literal, i.e., the variable , or , or (when the variable does … Continue reading

April 1, 2011 · 1 Comment

Order (and small disorder)

In most textbooks, one finds that a category represents a preorder exactly when there is at most one arrow between any pair of objects. But, surprisingly, the same is told … Continue reading

March 29, 2011 · Leave a comment