DocumentCode :
2169893
Title :
The resolution complexity of random constraint satisfaction problems
Author :
Molloy, Michael ; Salavatipour, Mohammad
Author_Institution :
Dept. of Comput. Sci., Toronto Univ., Ont., Canada
fYear :
2003
fDate :
11-14 Oct. 2003
Firstpage :
330
Lastpage :
339
Abstract :
We consider random instances of constraint satisfaction problems where each variable has domain size d, and each constraint contains t restrictions on k variables. For each (d, k, t) we determine whether the resolution complexity is a.s. constant, polynomial or exponential in the number of variables. For a particular range of (d, k, t) we determine a sharp threshold for resolution complexity where the resolution complexity drops from a.s. exponential to a.s. polynomial when the clause density passes a specific value.
Keywords :
computability; computational complexity; constraint theory; random processes; clause density; constant resolution complexity; domain size; exponential resolution complexity; polynomial resolution complexity; random constraint satisfaction problems; resolution complexity; restrictions; variables; Artificial intelligence; Chromium; Computer science; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
ISSN :
0272-5428
Print_ISBN :
0-7695-2040-5
Type :
conf
DOI :
10.1109/SFCS.2003.1238207
Filename :
1238207
Link To Document :
بازگشت