تقرير
An Arithmetic Theory for the Poly-Time Random Functions
| العنوان: | An Arithmetic Theory for the Poly-Time Random Functions |
|---|---|
| المؤلفون: | Antonelli, Melissa, Lago, Ugo Dal, Davoli, Davide, Oitavem, Isabel, Pistone, Paolo |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Computational Complexity, Computer Science - Logic in Computer Science |
| الوصف: | We introduce a new bounded theory RS^1_2 and show that the functions which are Sigma^b_1-representable in it are precisely random functions which can be computed in polynomial time. Concretely, we pass through a class of oracle functions over string, called POR, together with the theory of arithmetic RS^1_2. Then, we show that functions computed by poly-time PTMs are arithmetically characterized by a class of probabilistic bounded formulas. Comment: 37 pages, pre-print |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2301.12028 |
| رقم الأكسشن: | edsarx.2301.12028 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |