๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The Resolution Complexity of Random Constraint Satisfaction Problems

โœ Scribed by Molloy, Michael; Salavatipour, Mohammad R.

Book ID
118181276
Publisher
Society for Industrial and Applied Mathematics
Year
2007
Tongue
English
Weight
334 KB
Volume
37
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Resolution Complexity of Random Constrai
Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
โœ Yong Gao; Joseph Culberson ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 97 KB

Let C 2,k,t n,cn be a random constraint satisfaction problem(CSP) of n binary variables, where c > 0 is a fixed constant and the cn constraints are selected uniformly and independently from all the possible k-ary constraints each of which contains exactly t tuples of the values as its restrictions.