I'll be attending

Highlands Workshop on XML, Logic, and Automata organized by Leonid from tomorrow until this Sunday. The venue is actually quite interesting: a small town in the Highlands called

Grantown-on-spey. I'm just hoping that they have a grocery store :) I will give a presentation on recurrent reachability in regular model checking based on

this paper. Anyway, I'll post a summary of the workshop later on this week.

## 1 comment:

SAT is (not) NP-complete

http://arxiv.org/abs/0806.2947

Here is a easy-to-understand for this:

Let L be the Prolog program:

Fact:

Age-About-21(John,0.9).

Goal:

?- Age-About-21(John,0.9).

The Prolog system answers two different contradictory answers:

"Yes" = "1" and "0.9" in the fact.

Try the goal:

?- Age-About-21(John,0.3).

Again, the system answers two contradictory answers:"No" = "0" and "0.9".

Clearly, this language is in P, but how to reduce it to SAT?

How to reduce instances of the FLP problem whose output is two contradictory truth values to the SAT problem whose output is only one.

It is easy to show that ZFC is inconsistent via 2 (independent) proofs.

Post a Comment