کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4662583 | 1633498 | 2011 | 28 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The provably total NP search problems of weak second order bounded arithmetic
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
منطق ریاضی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We define a new NP search problem, the “local improvement” principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in , it characterizes the consequences of and that natural restrictions of it characterize the consequences of and of the bounded arithmetic hierarchy. We also show that over V0 it characterizes the consequences of V1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the consequences of . Throughout our search problems are “type-2” NP search problems, which take second-order objects as parameters.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 162, Issue 6, April–May 2011, Pages 419-446
Journal: Annals of Pure and Applied Logic - Volume 162, Issue 6, April–May 2011, Pages 419-446