کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429921 687723 2007 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله 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