Thursday, October 16, 2014

CNF restrictions that lead to exponential speedup

Blogposts are good place to write things up, because they do not magically disappear as most of the handwritten notes on my desktop. I was creating a list of different types of CNF formulas to mark which restrictions makes counting solutions or deciding satisfiability polynomial computable. Such an overview is certainly not new but i did not find a sufficiently complete list. So i tried to come up with such a list by myself and thought it could be of some interest for you. The restrictions i was aiming at have the following abbreviations:
  • $\text{Ex3SAT}$ : Each clause has exact $3$ variables
  • $\text{Pl}$ : The incidence graph of a formula $\Phi$ is planar
  • $\text{Tree}$ : The incidence graph of a formula $\Phi$ is a tree
  • $\text{Mon}$ : Monotone, i.e., each variable occurs only in positive form
  • $\text{Rtw}$ : ReadTwice, i.e., each variable occurs at most twice
  • $\text{x-in-N}$ : Exactly $x$ variables out of $N$ must be true in each clause. So $\text{1-in-3-3CNF}$ also forces that each clause has exactly 3 variables and not less. So $\text{1-in-3-Ex3CNF}$ is actually the same.
  • $\text{RtwOpp}$ : The variable occurs twice but in opposite value, i.e., once negative and once positive
  • $\text{Nae}$ : Not all equal, i.e., in a satisfying assignment, at least one variable in a clause must be false
Note, if you know the number $1-in-3$ solutions of a formula $\Phi$, then if you negate all variables, you get a $2-in-3$ solution.

Thursday, September 04, 2014

Learning a Sine-Wave (Part 2) - A partial solution

For convenience, i restate the problem definition here:
Problem-Definition. Assume you have an integer interval $I = [0,n]$ and a set $Z$ that consists of tuples $(x,s(x))$, with $x \in_R I$ and $s(x) = \text{sign}(\sin(2x\pi/p))$. Find the secret parameter $p$.

Formulated in words, the set $Z$ contains randomly distributed integers from $I$ enriched with the information if a certain (but fixed) sinus wave travels above or below that integer (i.e. the sign value) and your goal is to find that particular sine wave.

Heuristically, $\log p$ points should be sufficient, and in the first part on this topic, i described an easy instance of this problem that indeed finds $p$ using only $\mathcal{O}(\log p)$ points. Then i showed what causes the algorithm to fail if the problem instance gets a little bit more complicated. The algorithm then fails because the solution space falls apart (this could be very well shown visually if the solution spaces are drawn on a unity disk) and keeping track all the scattered solution spaces is too inefficient.

Monday, August 04, 2014

A world where NP = P

During the last months i spent some of my free time to read several books and interesting articles. E.g. "The Golden Ticket: P, NP, and the Search for the Impossible" by Lance Fortnow or Scott Aaronson's "Quantum Computing since Democritus".

In the former the author describes in one chapter how the world would look like if P = NP. He is by no way the first who thinks and writes about this, but he did it in a very extensive and pictured way. It was intriguing to read what kind of things would become possible if this rather mathematical problem would be solved. The world can be described at best with "Everything that we can quickly recognize as being a good solution for a problem, we can find quickly" But more on this later.

Of course, an existential proof would not change much, besides the receipt of one million dollars from the clay institute. If you just prove that there has to be an algorithm that could solve the traveling salesmann problem in polynomial time, but not how to find it, you are not very closer to the beautiful world as before the proof was discovered.

Eeeh, thats not completely true. You will not be closer in terms of real progress, but you will be "closer" terms of confidence. The difference is, after the theoretical proof has been given, that you know that there is an algorithm and that it could be found. The search maybe fail because of other reasons, e.g., the algorithm is so different than usual algorithms that you always look into the wrong direction or that minimum length of the algorithm is, because of what ever reasons, more than $2^{60}$ symbols. But whatever the case maybe, the world will keep on searching...



And then out of nowhere, a young CS graduate comes around with a beautiful idea. He found a way how to solve an $n^2 \times n^2$ sudoko puzzle in $\mathcal{O}(n^{33})$ steps. And he found it simply because it was a mid-game puzzle in the latest version of Super Mario Brothers :)

And that's the start.

Since sudoko is NP-complete, you can transform other problems into a sudoko puzzle and run your algorithm. The transformation maybe cumbersome and inefficient and even the runtime of $\mathcal{O}(n^{33})$ is too much for our daily computers. And in the first month, despite having an algorithm from P at hand, it could still not very useful.      But there is hope.

The hope arises from the algorithm itself. As noted above, the algorithm has the property that it could be used to find a good solution quickly (as long as you known what is good). And here good = quick/fast/efficient. So feeding the algorithm with itself, will generate an efficient solution efficiently, or lets say, a faster solution fast. And if one round is not sufficient, you can keep looping this procedure until you reach a version that runs fast enough and eventually uses so few space/memory that it can be executed on your new smartphone.

So, what are the changes?

The changes are numerous, life-changing but sometimes two sided.

First of all, the discovery of the algorithm leads to several positive monetary aspects, like scheduling flights more efficiently to decrease time delays or better routing the decrease kerosine consumption for airlines.

These positive effects probably effect all areas where things have to be scheduled or events have to be synchronized. But since all companies get effected by this positive trend, nobody gains a real advantage. And probably none of this, except you are working in such a business, you will personally notice very much nor will change your life nor will make very happy.

What you will notice personally will be the increased reliability of weather forecasts. The new algorithm allows to predict rainy or sunny days about 365 days ahead. Fortnow describes in a funny way how this ability will influence the price for weather dependent events in a dramatic way. Nobody wants to marry on a cold and rainy day, so the price for the sunny days will rise to compensate the rainy ones. The knowledge of the rainy weeks in otherwise sunny countries will decrease the number of booking for these weeks and on sunny weeks all hotels will be completely full.

On the other side, a lot of people could be saved because hurricanes and tornadoes could be predicted way ahead and all houses would be empty if the tornado finally arrives.



But there will also be a bigger change and you will probably benefit from it at some point in your life. And this change is the new effectiveness of personal medicine.

What Fortnow describes in his book maybe at little bit to optimistic or at least in my view. But i think it is probably the most important improvement that this algorithm could bring to the world. 

Proteins are important building blocks for our body and are responsible for many actions and reactions in the human body. These large molecules could be disassembled into a linear chain of amino acids. But its activity is determined by its three dimension structure. I.e. how this string folds into the 3 dimensional space. And the computation of this protein folding is a NP-complete problem [1]. That means, given a list of the amino acids, the difficult task is to predict its three dimensional structure. I am not a chemist or biologist, but i once learned that this would be extremely useful. Fortnow describes, that one would use this to completely get rid of things like cancer. You just have to go to the hospital where your blood and the cancer cells are analysed. Then an amino sequence is generated and folded in such a way, that these molecules do only one job; no ifs no buts and no side effects; just one job - kill these cancer cells. And after one week with one pill each day, you will be well again.

I have some doubts regarding this. The discovery of the algorithm should change the world from today, were each year ~ 8.000.000 people die from cancer to a world where cancer is nothing more than a slight headache.  The algorithm makes the generation of this personalised cancer pill fast and cheap. What i wonder about is, what about approximations? Even today for several NP-complete algorithms there are good approximation algorithms.

How about protein folding? Why aren't there some "approximated cancer pills" or is protein folding hard to approximate? Or is personalised medicine overrated and the described approach does not really work this way?

And this new medicine is also two sided. I bet that also drug dealers would use the algorithm to produce even better drugs; drugs that even create more addiction but do not harm the people in the way most of the current drugs do. So consumers can buy the drugs over many years without all the health-damaging risks but all the addictive behavior to make the dealers even richer.

You can also bet that the army will exploit the advantages of the algorithm in all direction. Build new weapons, better guiding software and the increase the destruction capabilities. For example the weapon target weapons allocation problem is known to be NP-complete.

I think that such an algorithm can not be found, since i believe that NP$\neq$P but sometimes i get doubts because the determinant can be computed efficiently ;)


[1] On the complexity of protein folding (extended abstract), Pierluigi Crescenzi, Deborah Goldman, Christos Papadimitriou, Antonio Piccolboni, Mihalis Yannakakis, Proceeding STOC '98 Proceedings of the thirtieth annual ACM symposium on Theory of computing Pages 597-603

Thursday, June 12, 2014

Discrete logarithms with auxiliary input

Auxiliary Input helps
The discrete logarithm problem with auxiliary input is defined as the problem to compute the integer $e$ given the input $(g,g^e = r,\mathcal{G})$, whereof $\mathcal{G}$ is an abelian group and $g$ is of prime order $p$ if one knows the additional input $$\left(g^{e^2},g^{e^3},...,g^{e^d}\right) \in \mathcal{G}^d$$ In [1] Jung Hee Cheon presents an algorithm which solves the problem in $\mathcal{O}(\sqrt{p/d} + \sqrt{d})$ using $$\mathcal{O}\left(\max\left(\sqrt{(p-1)/d},\sqrt{d}\right)\right)$$ space if $d | (p-1)$. The algorithm works even if the input is reduced to $(g,g^e=r,\mathcal{G},g^{e^d},d)$ only.

If $p|(p+1)$ he shows how to solve the problem given the full input in $\mathcal{O}\left(\sqrt{p/d} + d\right)$ using the same amount of space as in the case $p|(p-1)$.

Wednesday, May 21, 2014

Estimating discrete logarithms via sum of group elements

The discrete logarithm problem is one of the cornerstones of modern asymmetric cryptography. Several algorithms exist and each approaches the problem in different ways. For example, the Pohlig-Hellman algorithm exploits smooth group orders, the index calculus algorithm uses a small set of known discrete logarithms in order to combine them to solve the problem in question and Pollards Rho-Algorithms makes use of the birthday paradox.

I am not aware of any approach that makes use of the fact, that the residues $r_i$ in the group $\mathcal{G} \subseteq \mathbb{F}_p$ generated by the element $g$ are often nearly equal distributed. Ok, this is not always true and there are some deep and highly non-trivial theorems about the distribution of these group elements. But for our purposes we can assume that the average size of a group element is $(p-1)/2$. That means, if we assume that $g$ is a primitive root, hence $\mathcal{G} = \mathbb{F}^*_p$, and $r_i \equiv g^i\pmod{p}$ it holds: $$ \sum^e_{i=1} r_i \approx e\cdot \frac{p-1}{2} $$ And since $e < p$ it in particular holds $$ S := \sum^e_{i=1} r_i = e\cdot \frac{p-1}{2} + \mathcal{O}(p^{1/2}) < p^2 $$ So if we can compute $S$ we get a very good approximation of $e$ since $$ \frac{2\cdot S}{p-1} = e + \mathcal{O}(1) $$

Tuesday, May 06, 2014

Factoring to SAT

Creating hard instances of computational problems can be easy (e.g., Factoring), cumbersome (e.g, SAT) or hard (e.g. Graph Isomorphism). So using a problem that allows to create instances in an easy way and then transform it into an instance of another problem is often a good idea, as long as the transformation is feasible. In this post i want to show how factoring can be reduced to a boolean formula $\varphi$ such that finding a satisfying assignment of $\varphi$ reveals a factor of the original integer. So if you think you found an algorithm that solves SAT in polynomial time, you should use this approach to convert a 2048-bit RSA instance to a SAT instance and test how it behaves :)

The approach is analogous to the approach of ToughSAT. For a high level overview, the algorithm works like this:

Input: $N = pq$, with unknown primes $p$ and $q$.
  1. $n \leftarrow$ bitlength(N)
  2. Take $2n$ variables for the binary representation of $p$ and $q$ and write:
    \begin{align*}
    x_{n-1}x_{n-2}...x_1x_0 \cdot y_{n-1}y_{n-2}...y_1y_0
    \end{align*} Then apply the school method for multiplying two integers.
  3. This multiplication creates a list of equations that heavily depend on each other.
  4. Replace each equation with an equivalent formula that only uses the boolean operators "and" and "or".
  5. Transform the boolean formula to a 3CNF
I will present the algorithm by an example:

Thursday, April 24, 2014

Holographic Algorithms

This post shows an introduction to Holographic Algorithms (HA). From my point of view, Holographic Algorithms were motivated by analogies to quantum computing and to overcome some of the obstacles that occur when one follows Leslie Valiant's original approach using the permanent and cyclic covers to count satisfying solutions for boolean formulas.

Again, the basic ingredient for HAs is the efficiently computable FKT-algorithm, which works because of the grateful fact that we are able to compute the determinant in polynomial time.

The literature of Holographic Algorithms (which are a generalization of CSP-Problems) is huge and is dominated by works of Valiant, Cai and Lu, see e.g. [1,2,3]. The central theorem is the Holant Theorem, which proofs the equality of the number of perfect matchings of a graph $\mathcal{G}$ and the value of the Holant Function. The Holant Function is applied to a matchgrid, that is a graph composed of certain subgraphs (called matchgates), such that the total graph (the matchgrid) is the graph $\mathcal{G}$ and its structure incorporates a combinatorial function.
The matchgrid $\Omega$ can be seen as a bipartite graph whereof the matchgates are the vertices. For the application to count satisfying assignments, we are always faced with bipartite graphs: on the left are the variable nodes and on the right the clause nodes. 
The Holant Function can be understood as a function that measures or counts particles that flow along the lines of the bipartite graph from the left nodes to the right nodes, i.e., from the variables to the clauses.

For HA two types of mathgates are sufficient: Generators and Recognizer. The generator generates patterns of particles along its output lines and the recognizer recognizes these patterns. Matchgates, i.e., generators and recognizers, are little graphs with only output and input nodes respectively.

In Figure 1, you see a simple generator, which is the box on the left denoted as A. It is just a small graph that connects two nodes and has one edge of weight 1. The two nodes are also the output nodes (thats why they are drawn of the outerface of the matchgate). Normally, there are more inner nodes.
Figure 1 - A generator and its signature configurations

Friday, March 21, 2014

Weird exceptions

Some say Computational Complexity is all about the $1$-million worth question $$\mathsf{P} \overset{?}{=} \mathsf{NP}$$ Of course, this is far from being correct. There are many more complexity classes and many more models of computation. Technically, the two classes $\mathsf{P}$ and $\mathsf{NP}$ are not special. But they are of special interest, since they pose a barrier between what perhaps can be computed on our classical computers in a feasible amount of time and those problems that in many cases would require an exponential amount of time. Or, spoken in a more simple way, they show up the barrier between what can be computed and what can not be computed due resource constraints.

However, there are some problems that have some weird special cases, which seem to be missed accidentally by the claws of the $\mathsf{NP}$ monster and fell into the lower class of $\mathsf{P}$. Both examples are actual based on the beautiful work of Leslie Valiant who showed how to connect the problem to count satisfying assignments to counting perfect matchings in planar graphs. The first one is:

$\#_2$ $\mathsf{PL}$-$\mathsf{RTW}$-$\mathsf{MON}$-$3\mathsf{CNF}$ vs. $\#_7$ $\mathsf{PL}$-$\mathsf{RTW}$-$\mathsf{MON}$-$3\mathsf{CNF}$


Tuesday, March 04, 2014

An implementation of the FKT-algorithm

This post is dedicated to give you an implementation (in SAGE) of the FKT-algorithm. I coded this while spending some time on the ideas i explained in this blog post. I searched several hours to find an existing implementation without success. Since it took me a while to code this on my own, i think it is worth to present it, therewith other can use it in their own work. It works well, but if you find an error, please leave a note.

The FKT-algorithm can be used to count the number of perfect matchings in a planar graph. And a graph is planar if and only if it does not have K$_5$ or K$_{3,3}$ as a minor.

A paper that will be presented at the CCC conference this year is called:
Counting the Number of Perfect Matchings in $K_5$-free Graphs [in polynomial time] Simon Straub (Ulm University), Thomas Thierauf (Aalen University), Fabian Wagner (Ulm University)
I did not manage to read it yet, but i am curious to see, how they circumvent the K$_{3,3}$ minor problem.

########################################################################
# AUTHOR: Dr. Christian Schridde
# E-MAIL: christianschridde [at] googlemail [dot] com
#
# DESCRIPTION: Implementation of the FKT-algorithm
#
# INPUT:  Adjacency matrix A of a undirected loop-free planar graph G
# OUTPUT: Skew matrix M, such that PerfMatch(G) = Sqrt(Determinat(M))
########################################################################

Thursday, February 27, 2014

The Graph Isomorphism Problem

The graph isomorphism ($\mathsf{GI}$) problem is one of the few known problems in computational complexity that are in the complexity class $\mathsf{NP}$, but neither known to be in $\mathsf{P}$ nor in $\mathsf{NP}$-complete. So it is a very good candidate for a so called $\mathsf{NP}$-intermediate problem. Another well known candidate is factorization.
For many types of graphs the $\mathsf{GI}$ problem could be solved efficiently, i.e., using only poly($n$) many resources, whereof $n$ is the number of vertices in the graph. However, one is able to generate hard instances where all the algorithms fail and an exponential amount of resources is needed in order to solve the problem. But finding such hard instances is not easy. In particular for random graphs, the isomorphism problem is almost always easy. So the average complexity of $\mathsf{GI}$ is low, but the worst case complexity is hard.

Definition [Graph Isomorphism] Two graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$ are isomorphic if there is a bijective mapping $\sigma: V_1 \rightarrow V_2$ such that if there is an edge between the vertices $u$ and $v$ in $G$, i.e., $(u,v) \in E_1$, then there is an edge between the vertices $\sigma(u)$ and $\sigma(v)$ in $H$, i.e. $(\sigma(u),\sigma(v)) \in E_2$.

The actual description of the problem is easy and understandable even to people that perhaps see graphs first their first time. In Figure 1 the undirected graph $G$ is shown.
Figure 1 - The graph $G$
$G$ has $8$ vertices and each one is of degree $3$. In Figure 2 you can see the two graphs $H_1$ and $H_2$. One of these is isomorphic to $G$ and the other one is not.

Figure 2 - On the left it is graph $H_1$ and on the right $H_2$
Question: Suppose you could drag each vertex with your mouse. Which set of vertices can be rearranged such that the graph $G$ appears? That means, is $G \cong H_1$ or $G \cong H_2$?

Tuesday, February 11, 2014

The sum of integers is -1/12 ... or not?

In the current days it seems that people picked up an old discussion and brought it to new attention in their forums. In heated debates they discuss and exchange their point of views, sometimes rather impolite than objective.

They talk about infinite sums of integers, in particular divergent sums, and show how these sums can be manipulated to be equal to a finite value. This causes trouble, since it seems on the first sight rather unintuitive and wrong.

The most used example for their offending object is the simple sum $$1 + 2 + 3 + 4 + ... = \sum^\infty_{i=1} i$$, which can be manipulated such that it is finally equal to $-1/12$. The first one who showed this curiosity was the famous mathematician Srinivasa Ramanujan. And from the fact that a credible mathematician wrote down those things, there should arise some doubt that maybe perhaps there is some truth in these formulas and that the misunderstandings come from the fact, that the formulas are probably not correctly cited and used.

Thursday, January 30, 2014

What if $\sigma_0(n)$ could be computed efficiently? (Part 3)

The $\sigma_i(n)$ function is an important arithmetic function and as typical for such functions, it can not be computed efficiently for large input parameters $n$ due to the factorization problem. But in contrast to $\sigma_1(n)$, which does reveal the factorization of $n$ immediately (at least if $n=pq$), $\sigma_0(n)$ does not, or at least not that easy (see Part 2 and Part 1). Additionally, $\sigma_1(n)$ has also the strange property that it can be computed recursively, as i showed in that [post].

However, we know how to compute, or better, how to decide, if $\sigma_0(n)$ is $2$ or not. This is because $\sigma_0(n) = 2$ if and only if $n$ is a prime number. And primality can be checked by the AKS-Algorithm in deterministic polynomial time. If AKS is too slow for you, there much more faster probabilistic polynomial time algorithms. They utilize that a prime number has special properties, e.g., they use Fermat-Little-Theorem. But so called base-$b$ pseudo prime numbers can survive this process and still pretend to be a prime number. Repeating the whole process with different values for $b$ often helps. Only a few pseudo prime numbers still remain for nearly all choices of $b$. These numbers are called carmichael numbers, and in [1] it was proved that there are infinite many such numbers. However, the probability to announce a false-positive for such algorithm is negligible after a few rounds.

Thursday, January 16, 2014

What if $\sigma_0(n)$ could be computed efficiently? (Part 2)

In the first post regarding this topic, i sketched why an algorithm that counts the number of prime factors of an integer could lead to an algorithm that actually could factorize that integer. The application of such an algorithm to different number fields would lead to non-trivial information about the prime factors due to the definition of prime numbers in $\mathbb{Q}(\sqrt{d})$. The hope is, that this information would eventually allow us to reconstruct the entire prime numbers.

In this post i will show some basic facts about different number field and what information they leak about prime factors of $n$ if $\sigma_0(n)$ is known.

Sunday, January 12, 2014

Brainteasers

Brainteasers become more and more popular in these days. You hear them from friends, in bars, read them on blogs and they are even used in job interviews to puzzle the candidates. Some of them are easy and some of them are tricky and some of them are really hard.

A common teaser for example is:

"A melon weights 1200gr and contains 99% water. Suppose that after one week the amount of water has reduced to 98%. What is the new weight of the melon?"

[Spoiler Start: White-on-White / Mark with the mouse]
It is 600gr! Just observe that the $1200$gr is made up of  $99\%$ water and $1\%$ melon-meat. That are $1188$gr water $12$gr melon-meat. After one week the weight of the melon reduces the $x$gr, whereof $y$gr are water and still $12$gr melon-meat. And it is known that the $y$gr water are now $98\%$, hence the $12$gr melon-meat must be $2\%$. But if $2\%$ are $12$gr, then $100\%$ are $600$gr.
[Spoiler End]