Font Size:
Extremely Complex Boolean Problems a Challenge for Mathematics and Informatics
Last modified: 2014-02-13
Abstract
The theory of complexity allows us to classify given problems with regard to their complexity. We can be happy when the problem to be solved belongs to the class of logarithmic, linear, or polynomial complexity. But what can be done when the problem belongs to the most difficult exponential complexity? The number of function values of a Boolean function exponentially depends on the number of their variables. Hence, most of the Boolean problems have an exponential complexity depending on the number of variables.
Within these classes the factual complexity of a problem can be measured by the required space to store all data, by the number of operations, or by the expected time to solve the problem. It is a challenge for mathematicians and computer scientists to solve extremely complex tasks where the basically required resources are beyond all realistic limits. The number of such extremely complex Boolean problem grows due to the progress in microelectronics as well as in science. The topic of this paper is to show how Mathematics and Informatics may successfully contribute to the solution of extremely complex Boolean problems.
We take as example the edge coloring of complete bipartite graphs without complete monochromatic subgraphs K2;2. This task is equivalent to the rectangle-free coloring of grids using four colors. Before our recent solution it was an open question whether such colorings of the grids of the sizes 17x17, 17x18, 18x17, and 18x18 exist. The number of different 4-color patterns of the grid 18x18 is equal to 4^324~1.16798*10^195. Due to this complexity it seemed to be hopeless to find solutions. Up to now, most powerful SAT-solvers were able to find solutions for subproblems with the size of approximately 10^135. Hence, it was our challenge to bridge the gap of 10^60. We summarize in this paper several approaches in order to gain the required knowledge to find the solution.
Within these classes the factual complexity of a problem can be measured by the required space to store all data, by the number of operations, or by the expected time to solve the problem. It is a challenge for mathematicians and computer scientists to solve extremely complex tasks where the basically required resources are beyond all realistic limits. The number of such extremely complex Boolean problem grows due to the progress in microelectronics as well as in science. The topic of this paper is to show how Mathematics and Informatics may successfully contribute to the solution of extremely complex Boolean problems.
We take as example the edge coloring of complete bipartite graphs without complete monochromatic subgraphs K2;2. This task is equivalent to the rectangle-free coloring of grids using four colors. Before our recent solution it was an open question whether such colorings of the grids of the sizes 17x17, 17x18, 18x17, and 18x18 exist. The number of different 4-color patterns of the grid 18x18 is equal to 4^324~1.16798*10^195. Due to this complexity it seemed to be hopeless to find solutions. Up to now, most powerful SAT-solvers were able to find solutions for subproblems with the size of approximately 10^135. Hence, it was our challenge to bridge the gap of 10^60. We summarize in this paper several approaches in order to gain the required knowledge to find the solution.
Keywords
Artificial Intelligence; Four-valued Edge Coloring; Complete Bipartite Graph; Rectangle-free Grid; Boolean Equation; SAT-solver; XBOOLE