کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657751 | 690565 | 2005 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
All superlinear inverse schemes are coNP-hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. To do so, we develop a novel proof technique that builds diagonalizations against certificates directly into a circuit.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 345, Issues 2â3, 22 November 2005, Pages 345-358
Journal: Theoretical Computer Science - Volume 345, Issues 2â3, 22 November 2005, Pages 345-358
نویسندگان
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel,