NL Is Strictly Contained in P
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916219937882112 |
|---|---|
| author | Flum, Santiago Montoya, J. Andres |
| author_facet | Flum, Santiago Montoya, J. Andres |
| contents | We prove that NL is strictly contained in P. We get this separation as a corollary of the following result: the set of context-free languages is not contained in NL. The reader should recall that CFL is contained in DTIME(n^3) |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_04840 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | NL Is Strictly Contained in P Flum, Santiago Montoya, J. Andres Formal Languages and Automata Theory 03D15 We prove that NL is strictly contained in P. We get this separation as a corollary of the following result: the set of context-free languages is not contained in NL. The reader should recall that CFL is contained in DTIME(n^3) |
| title | NL Is Strictly Contained in P |
| topic | Formal Languages and Automata Theory 03D15 |
| url | https://arxiv.org/abs/2304.04840 |