NP is contained in DTIME(n^O(log^{gamma}))
We use existential Diophantine predicates carefully reinterpreted over the reals and the time complexity of Tarski algebra to show that 3-CNF SAT is in n^O(log^{gamma} n) time for an absolute positive constant gamma.
שמור ב:
| מחבר ראשי: | |
|---|---|
| פורמט: | Artículo |
| יצא לאור: |
2014
|
| נושאים: | |
| גישה מקוונת: | https://arxiv.org/abs/1401.7480 http://arxiv.org/abs/1401.7480 |
| תגים: |
אין תגיות, היה/י הראשונ/ה לתייג את הרשומה!
|