دسترسی نامحدود
برای کاربرانی که ثبت نام کرده اند
دانلود کتاب A Survey of Lower Bounds for Satisfiability and Related Problems
دانلود کتاب بررسی مرزهای پایین برای رضایتمندی و مشکلات مرتبط
مشخصات کتاب
A Survey of Lower Bounds for Satisfiability and Related Problems
ویرایش:
نویسندگان: Dieter Melkebeek van
سری: Foundations and Trends(R) in Theoretical Computer Science
ISBN (شابک) : 1601980841, 9781601980854
ناشر: Now Publishers Inc
سال نشر: 2007
تعداد صفحات: 125
زبان: English
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود)
حجم فایل: 704 کیلوبایت
قیمت کتاب (تومان) : 44,000
در صورت تبدیل فایل کتاب A Survey of Lower Bounds for Satisfiability and Related Problems به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.
توجه داشته باشید کتاب بررسی مرزهای پایین برای رضایتمندی و مشکلات مرتبط نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.
توضیحاتی در مورد کتاب بررسی مرزهای پایین برای رضایتمندی و مشکلات مرتبط
NP-completeness مسلماً فراگیرترین مفهوم از علوم رایانه را تشکیل می دهد زیرا پیچیدگی محاسباتی هزاران مسئله مهم از همه شاخه های علوم و مهندسی را به تصویر می کشد. سوال P در مقابل NP می پرسد که آیا این مسائل را می توان در زمان چند جمله ای حل کرد؟ یک پاسخ منفی به طور گسترده برای مدت طولانی حدس زده می شود، اما، تا همین اواخر، هیچ مرز پایینی مشخصی در مدل های کلی محاسبات شناخته نشده بود. رضایت‌پذیری مسئله تصمیم‌گیری در مورد اینکه آیا فرمول بولی معین حداقل یک تخصیص رضایت‌بخش دارد یا خیر است. این اولین مسئله ای است که نشان داده شد NP-complete است و احتمالاً رایج ترین مسئله NP-complete مورد مطالعه است، هم به دلیل ویژگی های نظری و هم کاربردهای آن در عمل. بررسی مرزهای پایین برای رضایتمندی و مشکلات مرتبط، مرزهای پایینی اخیراً کشف شده برای پیچیدگی زمانی و مکانی رضایتمندی و مشکلات نزدیک به آن را بررسی می کند. این نتایج پیشرفته‌ترین مدل‌های محاسباتی قطعی، تصادفی و کوانتومی را مرور می‌کند و استدلال‌های اساسی را در یک چارچوب یکپارچه ارائه می‌کند. بررسی مرزهای پایین برای رضایتمندی و مشکلات مرتبط، مرجع ارزشمندی برای اساتید و دانشجویانی است که در زمینه نظریه پیچیدگی تحقیق می کنند یا برای انجام آن برنامه ریزی می کنند.
توضیحاتی درمورد کتاب به خارجی
NP-completeness arguably forms the most pervasive concept from computer science as it captures the computational complexity of thousands of important problems from all branches of science and engineering. The P versus NP question asks whether these problems can be solved in polynomial time. A negative answer has been widely conjectured for a long time but, until recently, no concrete lower bounds were known on general models of computation. Satisfiability is the problem of deciding whether a given Boolean formula has at least one satisfying assignment. It is the first problem that was shown to be NP-complete, and is possibly the most commonly studied NP-complete problem, both for its theoretical properties and its applications in practice. A Survey of Lower Bounds for Satisfiability and Related Problems surveys the recently discovered lower bounds for the time and space complexity of satisfiability and closely related problems. It overviews the state-of-the-art results on general deterministic, randomized, and quantum models of computation, and presents the underlying arguments in a unified framework. A Survey of Lower Bounds for Satisfiability and Related Problems is an invaluable reference for professors and students doing research in complexity theory, or planning to do so.
فهرست مطالب
Introduction......Page 12
Scope......Page 23
Organization......Page 25
Machine Models......Page 28
Complexity Classes......Page 29
Complete Problems......Page 33
Common Structure of the Arguments......Page 40
Direct Diagonalization Results......Page 42
Speeding Up Space-Bounded Computations Using Alternations......Page 45
Eliminating Alternations......Page 50
A Concrete Example......Page 51
Satisfiability......Page 54
Related Problems......Page 66
Nondeterministic Algorithms......Page 70
Somewhat-Nonuniform Algorithms......Page 76
Satisfiability and 2SAT......Page 88
Related Problems......Page 94
Randomized Algorithms with Unbounded Error......Page 98
Connection with Quantum Algorithms......Page 104
Future Directions......Page 112
Acknowledgments......Page 120
References......Page 122
