Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917917417799680 |
|---|---|
| author | Ali, Alejandro Mata |
| author_facet | Ali, Alejandro Mata |
| contents | In this paper we show that every combinatorial problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any combinatorial problem, both inversion, constraint satisfaction and optimization, by obtaining its equivalent tensor network. This formulation only requires a basic knowledge of classical logical operators, at a first year level of any computer science degree. These equations are not necessarily computable in a reasonable time, nor do they allow to surpass the state of the art in computational complexity, but they allow to have a new perspective for the mathematical analysis of these problems. These equations computation can be approximated by different methods such as Matrix Product State compression. We also present the equations for numerous combinatorial problems. This work proves that, if there is a physical system capable of contracting in polynomial time the tensor networks presented, every NP-Hard problem can be solved in polynomial time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05981 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN Ali, Alejandro Mata Emerging Technologies Quantum Physics 74P99, 81P68, 68R05, 68R10, 90C27, 90C05, 90C10, 90C20, 90C59 F.1.2; F.2.1; F.2.2; G.1.6; G.2.1; G.2.2 In this paper we show that every combinatorial problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any combinatorial problem, both inversion, constraint satisfaction and optimization, by obtaining its equivalent tensor network. This formulation only requires a basic knowledge of classical logical operators, at a first year level of any computer science degree. These equations are not necessarily computable in a reasonable time, nor do they allow to surpass the state of the art in computational complexity, but they allow to have a new perspective for the mathematical analysis of these problems. These equations computation can be approximated by different methods such as Matrix Product State compression. We also present the equations for numerous combinatorial problems. This work proves that, if there is a physical system capable of contracting in polynomial time the tensor networks presented, every NP-Hard problem can be solved in polynomial time. |
| title | Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN |
| topic | Emerging Technologies Quantum Physics 74P99, 81P68, 68R05, 68R10, 90C27, 90C05, 90C10, 90C20, 90C59 F.1.2; F.2.1; F.2.2; G.1.6; G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2502.05981 |