کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952329 | 1364440 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming](/preview/png/4952329.png)
چکیده انگلیسی
We study the probabilistic behaviour of solutions of random instances of the Boolean Satisfiability (SAT) and Constraint Satisfaction Problems (CSPs) that generalize the standard notion of a satisfying assignment. Our analysis focuses on a special type of generalized solutions, the (1,0)-super solutions. For random instances of k-SAT, we establish the exact threshold of the phase transition of the solution probability for kâ¤3, and give upper and lower bounds on the threshold of the phase transition for the case of kâ¥4. For CSPs, we derive an upper bound on the threshold of having a (1,0)-super solution asymptotically with probability 1, and establish a condition for the expected number of super solutions to grow exponentially.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 657, Part A, 2 January 2017, Pages 98-110
Journal: Theoretical Computer Science - Volume 657, Part A, 2 January 2017, Pages 98-110
نویسندگان
Peng Zhang, Yong Gao,