# Let's finish up ch. 6 with tree decomposition of CSPs (AIMA ch. 6).

• Jul 29, 2013 · 7:00 PM

It turns out that, by looking at the structure of a problem, we can find ways to solve it more efficiently; in particular, we can decompose a graph into a series of trees connected by a so-called "cutset". Trees can be solved (by topological sort) in linear time; fix the cutset, therefore, and solve the trees separately.

The cutset, on the other hand, can be n - 2 nodes in the worst case; so the actual savings are dependent on the topology of the problem.

• ##### Ryan H.

I ended up making some very significant improvements in the efficiency of my graph-based algorithm since I presented last week. In fact, there was a 99% decrease in run-time!

I doubt that I will be able to find time to tackle another aspect of CSP before we close out the subject. However if anyone is interested in propositional logic, we'll be journeying through SAT. It appears that while very closely related CSP and SAT are oddly orthogonal. Our notions of constraints and variables are almost reversed. However both are NP-Complete, and one can encode a CSP as a SAT or a SAT as a CSP. In the context of logic systems SAT looks to be more concise, but it seems unnatural for real-world expressive problems.

Here is a paper that exhaustively compares various mappings between the two:

July 27, 2013

• ##### Ryan H.

Also, the paper I showed quickly on the conversion of Non-Binary to Binary CSP indicates that it can in fact be done automatically, but that more research is necessary to determine when it may be beneficial. I dislike the graph they use to show it, but it seems that the conversion is definitely worthwhile if there are fewer constraints or if the constraints are exceptionally constrictive - at least for their problem.

July 27, 2013

• ##### Peter D.

Fantastic, man; can't wait to see it.

July 27, 2013

### Mountain View, CA

Founded May 23, 2012

#### People in this Meetup are also in:

• ##### SF Bay ACM Chapter

5,047 Members and Guests

• ##### Bay Area Infracoders

1,370 Infracoders

• ##### Silicon Valley Machine Learning

7,835 Data Coders

• ##### Silicon Valley Cloud Computing

8,681 Cloudsters

• ##### Autonomous Vehicle Enthusiasts

2,577 soon to be hands-free drivers

• ##### Palo Alto Data Science Association

2,481 Data Scientists