On state space structure and average case complexity in random K-SAT problems
John Ardelius · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2008
This thesis gives an introduction to a currently active area in the cross-section between theoretical computer science and theoretical physics. In the last ten years it has been suggested that critical behaviour, usually seen in models from condensed matter physics, may be responsible for the intractability of NP complete computation problems. This would suggest a very deep connection between the two fields on the most fundamental level. How deep this connection really is is subject to ongoing research as well as the topic of this thesis. Some of the conjectrues from the physics community regarding computational hardness in certain problem classes has turned out to be wrong or misinterpreted but the gained interest in both fields has promising potiential in moving the research frontier forward. The material presented in this thesis is the result of nearly two years work in trying to clearify how the results from physics can be interpreted in the language of actuall computation problems.