Some NP Complete Problems Based on Algebra and Algebraic Geometry
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910883215572992 |
|---|---|
| author | Hriljac, Paul |
| author_facet | Hriljac, Paul |
| contents | This paper describes several new problems and ideas concerning algebraic geometry and complexity theory. It first uses the idea of coloring graphs with elements of finite fields. This procedure then shows that graph coloring problems can be converted into membership problems for a new family of algebraic varieties, coloring varieties, which are closely related to determinantal varieties. This in turn shows that the problem of NP vs P can be converted into questions of if certain polynomials of large degree over finite fields have low multiplicative complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_14715 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Some NP Complete Problems Based on Algebra and Algebraic Geometry Hriljac, Paul Algebraic Geometry Commutative Algebra This paper describes several new problems and ideas concerning algebraic geometry and complexity theory. It first uses the idea of coloring graphs with elements of finite fields. This procedure then shows that graph coloring problems can be converted into membership problems for a new family of algebraic varieties, coloring varieties, which are closely related to determinantal varieties. This in turn shows that the problem of NP vs P can be converted into questions of if certain polynomials of large degree over finite fields have low multiplicative complexity. |
| title | Some NP Complete Problems Based on Algebra and Algebraic Geometry |
| topic | Algebraic Geometry Commutative Algebra |
| url | https://arxiv.org/abs/2503.14715 |