کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875711 1441981 2018 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A transfer method from bounded existential Diophantine equations to Tarski algebra formulas
ترجمه فارسی عنوان
یک روش انتقال از معادلات دیوفانتین وجودی محدود به فرمدهای جادو تارسکی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We identify a transfer method from bounded existentially quantified Diophantine equations to formulas of Tarski algebra, the first order theory of the real field. The method is applied to show that NP is contained in ⋃n=1∞Dtime(2a⋅logO(1)n), where a depends only on the given Diophantine equation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 708, 17 January 2018, Pages 91-95
نویسندگان
,