# CSP Notes

## Interesting tidbits
- Sometimes a CSP is called a "database" because the theory of CSPs and relational databases overlap. A CSP over a finite domain is the same thing as a relational database. A CSP instance can be called a "query" of the database.
- An "instance" is a particular representation of a CSP, with variables and constraints enumerated. An example of two different instances of the same CSP are $X_1 = \{x\}$, $C_1 = \{x(x-1)(x-2)(x-3)\}$ vs $X_2 = \{x, b_0, b_1\}$, $C_2 = {b_0^2 - b_0, b_1^2 - b_1, x - 2b_1 - b_0}$. Both instances constrain $x$ to be 0, 1, 2, or 3 despite having different variable sets and constraint sets.
- The proofs that ZKPs exist was based on graph coloring.
- Intents can be formulated as CSPs.
- CSP solving can be distributed! Each solver gets a small portion of the CSP to examine and communicates with other solvers to reach a solution. This works best when the CSP is "sparse and loose", meaning each variable relates to just a few other variables and there are many satisfying assignments for each constraint.
- An example could be a CSP to find a small non-trivial Pythagorean Triple. Three solvers approach the problem, each focusing on a particular variable. Solver A focuses on the $a^2$ portion of the problem and makes an ordered list of a few possibilities: $(1, 4, 9, 16, 25)$. Solver B focuses on $b^2$ but is more optimistic, making a shorter list; $(1, 4, 9)$. Solvers A and B send their lists to Solver C, who makes a list of all possible sums of their value sets and puts them in order: $(2, 5, 8, 10, 13, 17, 18, 20, 25, 26, 29, 34)$. Meanwhile, the final Solver D makes an ordered list of possible values for $c^2$: $(1, 4, 9, 16, 25, 36)$. Solver C sends its list to Solver D, who searches for a match in the list. When the final solver finds a match, it sends its choice back to the other solvers who construct a solution $(3, 4, 5)$.

## Tweets
- For Anoma we are researching best ways to formalize *intents*. What precisely are they, what are their components, how do we combine intents efficiently, and so on.
- One important aspect of intents is *solving*. Solvers on the network will receive many complex intents to exchange assets under certain conditions. How do solvers find a transaction that satisfies them all? Is there even a transaction that satisfies *any* of the intents? If there are multiple satisfying transactions, how do they find the best ones?
- We are lucky, because most of the conditions on transactions contained within intents can be formulated as instances of Constraint Satisfaction Problems (CSPs) and solving instances of CSPs is a well-studied area.
- Some well-known CSPs are 2-SAT, 3-SAT, Diophantine equations, and the three-coloring of graphs. The proof that zero-knowledge proofs exist was based on graph coloring!
- CSPs are defined by a finite set of atomic relations over some domain. For instance 2-SAT is defined by the relations x OR y, x => y, and x NAND y over the domain {0, 1}. A combination of these relations is an instance of 2-SAT. Values of 0 or 1 can be assigned to each variable, and the assignment is called "satisfying" if it produces a "true" valuation.
- Some CSPs are pretty easy to solve if there is a solution, like 2-SAT. Others, like 3-SAT, are NP-Complete and there is no known efficient general algorithm for finding a satisfying assignment to a 3-SAT instance.
- Despite the lack of a general procedure for solving 3-SAT instances there are a variety of methods to solve special cases efficiently
- Being NP-Complete, any problem that is efficiently verifiable can be expressed as a 3-SAT problem. For this reason it is convenient to express problems in 3-SAT and use the methods that have been developed for 3-SAT to attempt to find a solution to the original problem.
- Remarkably, the act of solving CSPs can be distributed! This is great news for solvers on the Anoma network. Solvers can receive pieces of a CSP instance and find satisfying assignments for it (or narrow down the solution space) and pass on their findings to other solvers.
- Here's an example: Four Solvers need to find three natural numbers that form a Pythagorean triple, and solutions with smaller numbers are considered "better".
- Solver A focuses on the a^2 portion of the problem and makes an ordered list of a few possibilities: (1, 4, 9, 16, 25). Solver B focuses on b^2 but is more optimistic, making a shorter list; (1, 4, 9).
- Solvers A and B send their lists to Solver C, who makes a list of all possible sums of their value sets and puts them in order: (2, 5, 8, 10, 13, 17, 18, 20, 25, 26, 29, 34).
- Meanwhile, the final Solver D makes an ordered list of possible values for c^2: (1, 4, 9, 16, 25, 36). Solver C sends its list to Solver D, who searches for a match in the list. When the final solver finds 25 in both lists, it sends its choice back to the other solvers who construct a solution (3, 4, 5) they can all agree on.
- These notes are based on a report by Anthony Hart, who also helped with some corrections.