Unconventional complexity classes in unconventional computing (extended abstract)
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911888788422656 |
|---|---|
| author | Porreca, Antonio E. |
| author_facet | Porreca, Antonio E. |
| contents | Many unconventional computing models, including some that appear to be quite different from traditional ones such as Turing machines, happen to characterise either the complexity class P or PSPACE when working in deterministic polynomial time (and in the maximally parallel way, where this applies). We discuss variants of cellular automata and membrane systems that escape this dichotomy and characterise intermediate complexity classes, usually defined in terms of Turing machines with oracles, as well as some possible reasons why this happens. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16896 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unconventional complexity classes in unconventional computing (extended abstract) Porreca, Antonio E. Computational Complexity Many unconventional computing models, including some that appear to be quite different from traditional ones such as Turing machines, happen to characterise either the complexity class P or PSPACE when working in deterministic polynomial time (and in the maximally parallel way, where this applies). We discuss variants of cellular automata and membrane systems that escape this dichotomy and characterise intermediate complexity classes, usually defined in terms of Turing machines with oracles, as well as some possible reasons why this happens. |
| title | Unconventional complexity classes in unconventional computing (extended abstract) |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2405.16896 |