Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.18921 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912448818184192 |
|---|---|
| author | Keshavan, Anand Kumar Engineer, Sunu |
| author_facet | Keshavan, Anand Kumar Engineer, Sunu |
| contents | We propose the Transcendental Encoding Conjecture for decision problems, which asserts that every language in complexity class P encodes to an algebraic real (possibly rational or algebraic irrational) under its binary characteristic encoding or other relevant encodings, whereas every NP-complete language encodes to a transcendental real. In particular, we exhibit languages whose encodings are provably rational (hence algebraic), discuss the status of encodings for other "natural" languages such as PRIMES (its encoding is irrational but not known to be algebraic). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_18921 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Transcendental Encoding conjecture Keshavan, Anand Kumar Engineer, Sunu Computational Complexity We propose the Transcendental Encoding Conjecture for decision problems, which asserts that every language in complexity class P encodes to an algebraic real (possibly rational or algebraic irrational) under its binary characteristic encoding or other relevant encodings, whereas every NP-complete language encodes to a transcendental real. In particular, we exhibit languages whose encodings are provably rational (hence algebraic), discuss the status of encodings for other "natural" languages such as PRIMES (its encoding is irrational but not known to be algebraic). |
| title | Transcendental Encoding conjecture |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2506.18921 |