کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9655097 | 684025 | 2005 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of unfrozen problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the complexity of unfrozen problems On the complexity of unfrozen problems](/preview/png/9655097.png)
چکیده انگلیسی
We consider questions such as what is the complexity of recognizing instances of (monotonic) NP-complete problems in which no variable is fixed (or frozen) by the set of solutions. Since this unfrozenness is also a monotonic property in NP, this leads to an inductive sequence of properties for each monotone NP-complete property. In some cases the sequence remains NP-complete, while in others it at some point enters P. Determining the boundaries is particularly challenging. We also consider the related questions of recognizing maximal properties. This study was motivated by results from statistical mechanics being applied to phase transitions of NP-complete problems, which show a correlation of hard instances with a sudden increase in frozen variables.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 153, Issues 1â3, 1 December 2005, Pages 3-24
Journal: Discrete Applied Mathematics - Volume 153, Issues 1â3, 1 December 2005, Pages 3-24
نویسندگان
Adam Beacham, Joseph Culberson,