A transfer method from bounded existential Diophantine equations to Tarski algebra formulas

Autor:	Bruce Litow
Rok vydání:	2018
Předmět:	Algebra Discrete mathematics Transfer (group theory) General Computer Science DTIME Diophantine set Diophantine equation Bounded function Algebra over a field First order theory Theoretical Computer Science Mathematics Real field
Zdroj:	Theoretical Computer Science. 708:91-95
ISSN:	0304-3975
Popis:	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 ( 2 a ⋅ log O ( 1 ) n ) , where a depends only on the given Diophantine equation.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b8ff6677f6396a90c487afb43231c41b https://doi.org/10.1016/j.tcs.2017.10.013 Zobrazit plný text záznamu Full Text from ScienceDirect