Wednesday, July 16, 2008
Highland workshop on XML, Logic, and Automata
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.
Subscribe to:
Post Comments (Atom)
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