InterJournal Complex Systems, 26
Status: Accepted
Manuscript Number: [26]
Submission Date: 963011
Physics motivated approach to combinatorial optimization problems
Author(s): Wojciech Burkot

Subject(s): CX.07

Category: Brief Article


NP-complete combinatorial problems provide a good test of new algorithms for search and optimization. Many ideas for such algorithms like for example simulated annealing, orginated as models of physical processes. In other cases, an emergent property of a successful algorithm is similar to the behaviour of complex physical system exhibiting phase transition. Hovever, the most successful approach so far to this class of problems was to leave the physics analogy and concentrate on the fact that the problem complexity has its source below the dynamics layer of the physical system. Vice versa, looking for hidden complexity has proven sucessful in physics as well, where the observed properties of sufficiently complex systems, rather than dynamics itself, exhibit underlying symmetries.

The present paper is organized as follows. First, we present some background on combinatorial optimization. Second, we describe a method motivated by quark fragmentation for pruning an ineffective search for optima, together with a discussion of its usefulness for classical algorithms. In the end, we discuss the possible use of this method in quantum computation.

Retrieve Manuscript
Submit referee report/comment

Public Comments: