کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429921 | 687723 | 2007 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We show that the class is contained in ZPPNP. The proof uses universal hashing, approximate counting and witness sampling. As a consequence, a collapse first noticed by Samik Sengupta that the assumption NP has small circuits collapses PH to becomes the strongest version to date of the Karp–Lipton Theorem. We also discuss the problem of finding irrefutable proofs for in ZPPNP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 73, Issue 1, February 2007, Pages 25-35
Journal: Journal of Computer and System Sciences - Volume 73, Issue 1, February 2007, Pages 25-35