Oscillator Formulations of Many NP Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918142508269568 |
|---|---|
| author | Cai, Wenxiao Li, Zongru Wang, Yu-Neng Achour, Sara Lee, Thomas H. |
| author_facet | Cai, Wenxiao Li, Zongru Wang, Yu-Neng Achour, Sara Lee, Thomas H. |
| contents | Efficiently optimizing Nondeterministic Polynomial time (NP) problems in polynomial time has profound implications in many domains. CMOS oscillator networks have been shown to be effective and efficient in approximating certain NP-hard problems such as minimization of Potts Hamiltonian, and computational complexity theory guarantees that any NP problem can be reduced to it. In this paper, we formulate a variety of NP problems using first-order and multi-phase Potts Hamiltonian. We also propose a 3-state asymmetrically weighted oscillator optimizer design to optimize the problems. Building on existing knowledge in CMOS design, our proposed algorithms offer a promising pathway for large-scale optimization of NP problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13560 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Oscillator Formulations of Many NP Problems Cai, Wenxiao Li, Zongru Wang, Yu-Neng Achour, Sara Lee, Thomas H. Emerging Technologies Efficiently optimizing Nondeterministic Polynomial time (NP) problems in polynomial time has profound implications in many domains. CMOS oscillator networks have been shown to be effective and efficient in approximating certain NP-hard problems such as minimization of Potts Hamiltonian, and computational complexity theory guarantees that any NP problem can be reduced to it. In this paper, we formulate a variety of NP problems using first-order and multi-phase Potts Hamiltonian. We also propose a 3-state asymmetrically weighted oscillator optimizer design to optimize the problems. Building on existing knowledge in CMOS design, our proposed algorithms offer a promising pathway for large-scale optimization of NP problems. |
| title | Oscillator Formulations of Many NP Problems |
| topic | Emerging Technologies |
| url | https://arxiv.org/abs/2509.13560 |