Capturing relational NEXPTIME with a fragment of existential third order logic
We prove that the existential fragment Σ²<sub>1</sub><sup>,ω</sup> of the third or- der logic TO<sup>ω</sup> captures the relational complexity class non deterministic exponential time. As a Corollary we have that relational machines can simulate third order rel...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2015
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/50424 |
| Aporte de: |
| Sumario: | We prove that the existential fragment Σ²<sub>1</sub><sup>,ω</sup> of the third or- der logic TO<sup>ω</sup> captures the relational complexity class non deterministic exponential time. As a Corollary we have that relational machines can simulate third order relational machines. |
|---|