Tuesday, November 26, 2013

Convert Circuit SAT to K-SAT: De Morgan's laws is just a private case

Problem introduction

Convert Circuit SAT to $k$-SAT, so it will only include clauses with 1 to $k$ variables with signs $\in \left\{\lor,\lnot\right\}$ between them. And all the clauses will be separated by $\land$ sign.

Solution using De Morgan's laws

In the nested expressions, for each operation $(y \star z)$, where $y,z$ are *variables*, and $\star$ is some operation, you create a new variable, and replace the $(y \star z)$ with the new variable and adding the clauses from De Morgan's laws equation to the final solution.

Example: Let it be a Circuit SAT $a \oplus b \oplus c$.

  • Step one: Replace $a \oplus b$ with new variable $v1$. $v1 \equiv a \oplus b$
  • Step two: Add De Morgan's laws equation to the final solution. $(v1 \lor a \lor b) \land (a \lor \lnot b)$
  • Step three: Repeat it with the remaining variables $v1 \oplus c$ and you will get the final result: $(v1 \lor a \lor b) \land (a \lor \lnot b) \land (v2 \lor v1 \lor c) \land (v1 \lor \lnot c)$

Better way:

This could be solved using the truth table. It will take $2^n$ to build it, and while it seems like a lot, this is actually a very fast way. I show you how with our previous example.
Lets build a truth table for $a \oplus b \oplus c$
    a b c  result
    0 0 0 |0
    0 0 1 |1
    0 1 0 |1
    0 1 1 |0
    1 0 0 |1
    1 0 1 |0
    1 1 0 |0
    1 1 1 |1
Now lets take all the false cases and convert them to true by adding not to the entire expression, the result will be $k$-SAT, 3-SAT in this case:
$ (a \lor b \lor c) \land (a \lor \lnot b \lor \lnot c) \land (\lnot a \lor b \lor \lnot c) \land (\lnot a \lor \lnot b \lor c) $

Now lets try something more complicated: $(a \oplus b \oplus c) \lor \lnot(e \oplus f)$
To solve this lets first replace the expression $(a \oplus b \oplus c)$ with new variable $v1$. To do this lets build a truth table for $v1 \equiv (a \oplus b \oplus c)$
    a b c v1|solution
    0 0 0 0 |1
    0 0 0 1 |0
    0 0 1 0 |0
    0 0 1 1 |1
    0 1 0 0 |0
    0 1 0 1 |1
    0 1 1 0 |1
    0 1 1 1 |0
    1 0 0 0 |0
    1 0 0 1 |1
    1 0 1 0 |1
    1 0 1 1 |0
    1 1 0 0 |1
    1 1 0 1 |0
    1 1 1 0 |0
    1 1 1 1 |1
Now we can add the not of this table to the final result:

$(a \lor b \lor c \lor \lnot v1 \land) \land (a \lor b \lor \lnot c \lor v1) \land (a \lor \lnot b \lor c \lor v1) \land (a \lor \lnot b \lor \lnot c \lor \lnot v1) \land (\lnot a \lor b \lor c \lor v1) \land (\lnot a \lor b \lor \lnot c \lor \lnot v1) \land (\lnot a \lor \lnot b \lor c \lor \lnot v1) \land (\lnot a \lor \lnot b \lor \lnot c \lor v1)$

And now we are left with: $v1 \lor \lnot(e \oplus f)$ Lets create a truth table for it
    e f v1|result
    0 0 0 | 1
    0 0 1 | 1
    0 1 0 | 0
    0 1 1 | 1
    1 0 0 | 0
    1 0 1 | 1
    1 1 0 | 1
    1 1 1 | 1

And add the not to the finale equation we will get this final result:
$(e \lor \lnot f \lor v1) \land (\lnot e \lor f \lor v1) \land (a \lor b \lor c \lor \lnot v1 \land) \land (a \lor b \lor \lnot c \lor v1) \land (a \lor \lnot b \lor c \lor v1) \land (a \lor \lnot b \lor \lnot c \lor \lnot v1) \land (\lnot a \lor b \lor c \lor v1) \land (\lnot a \lor b \lor \lnot c \lor \lnot v1) \land (\lnot a \lor \lnot b \lor c \lor \lnot v1) \land (\lnot a \lor \lnot b \lor \lnot c \lor v1)$

This idea is easy to implement in to code. Converting Circuit SAT to K-SAT will be $O(2^CN)$ and it will produce less clauses and variables then using De Morgan's laws

Saturday, October 26, 2013

Big Plane

Solve TSP

I know that TSP optimal tour have no intersections, and I know that there are few routes that have no intersections. So I will find random non - intersections routes untill I be pleased.

How to find non intersection route?

Read input into cities array
do
  iterate over cities from i = 0
    iterate over cities from j = i
      if swapIfBetter(i, j) then set swapFound to true
while not swapFound

function swapIfBetter(index1, index2)
  if index1 equals 0 and index2 equals cities size - 1
    return false
 
 initialize cities a,b,c,d
 set a to cities at index index1
 set b to cities at index (index1 - 1) unless index1 equals 0 in that case set it to (cities size - 1)
 set c to cities at index index2
 set d to cities at index (index2 + 1) unless index2 equals (cities size - 1) in that case set it to 0

 initialize currentDistance1 to distance between a and b
 initialize currentDistance2 to distance between c and d

 initialize newDistance1 to distance between b and c
 initialize newDistance2 to distance between a and d

 if currentDistance1  + currentDistance2 < newDistance1 + newDistance2
   swap(index1, index2)
   return true
 end if
return false
end function swapIfBetter

function swap(index1, index2)
initialize newCities array

iterate over cities from i = 0 to index1
  add city from cities at index i to newCities

iterate over cities from i = index2 to index1
  add city from cities at index i to newCities

iterate over cities from i = index2 + 1 to cities size
  add city from cities at index i to newCities

set cities to newCities
end function swap













Friday, October 25, 2013

!(Intersections) == Optimal TSP route

It turns out that any optimal solution of TSP will have no intersections.

Here is the proof:

Lets assume we have an Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices. Now lets assume that the edge AB is intersecting the edge CD.

To find a shorter path all you have to do, is to switch between the connections of A and D so it will look like that:




You can do this because you do not change the number of edges connected to each vertex, you simply change the edges. In this example you removed AB and DC edges and added: AC and DB edges.

Also it will always produce shorter route than the original. In the next diagram I added a red lines for calculation only.
















EO is perpendicular to AC, and EF is perpendicular to DF. So now we have trinagels with 90 degree engle and we can tell that AO is bigger than AE and OC is bigger than EC and so is DO is bigger than DF and OB is bigger than FB. So we may say that AE + EC + DF + FB < AO + OB + OC + OD

And so we can say AC + DB < AB + DC. So by solving intersections in graph we can actually find a shorter paths and this is why there couldn't be any intersections in TSP optimal route.

Now the most interesting question is: Just how many non intersecting routes could be in Graph?