Coja-Oghlan, Amin (2009) Random constraint satisfaction problems. Electronic Proceedings in Theoretical Computer Science, Vol.9 . pp. 32-37. doi:10.4204/EPTCS.9.4 ISSN 2075-2180.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

Random instances of constraint satisfaction problems such as k-SAT provide challenging benchmarks. If there are m constraints over n variables there is typically a large range of densities r=m/n where solutions are known to exist with probability close to one due to non-constructive arguments. However, no algorithms are known to find solutions efficiently with a non-vanishing probability at even much lower densities. This fact appears to be related to a phase transition in the set of all solutions. The goal of this extended abstract is to provide a perspective on this phenomenon, and on the computational challenge that it poses.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Journal or Publication Title:	Electronic Proceedings in Theoretical Computer Science
Publisher:	Open Publishing Association
ISSN:	2075-2180
Official Date:	2009
Dates:	Date Event 2009 Published
Volume:	Vol.9
Number of Pages:	6
Page Range:	pp. 32-37
DOI:	10.4204/EPTCS.9.4
Status:	Not Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access (Creative Commons)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item