research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleKolmogorov complexity arguments in propositional logi
Bibtex cite IDRACTI-RU1-2009-22
Booktitle 7o Panellhnio Synedrio Logikhs (PLS07)
Year published 2009
Month July
We consider Boolean formulas with three literals per clause, or 3-SAT formulas. For random formulas with m clauses over n variables, such as r = m=n is a constant, it has been experimentally observed that, asymptotically as r crosses the threshold value 4:2 (approximately) the probability that Á is satis¯able falls abruptly from nearly 1 to 0. Moreover, as n increases towards larger and larger values, the transition of the probability becomes sharper. The purpose of this paper is to simply outline a connection between the problem of determining bounds to the threshold value and the concept of Kolmogorov complexity.
Spirakis, Paul
Stamatiou, Yannis
sfkolm_pls09_camera_ready.pdf (main file)
Publication ID665