DNA Probe Computing System for Solving NP-Complete Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908453644009472 |
|---|---|
| author | Xu, Jin Shi, XiaoLong Chen, Xin Wang, Fang Li, Sirui Ye, Pali Zhang, Boliang Deng, Di Kou, Zheng Qiang, Xiaoli |
| author_facet | Xu, Jin Shi, XiaoLong Chen, Xin Wang, Fang Li, Sirui Ye, Pali Zhang, Boliang Deng, Di Kou, Zheng Qiang, Xiaoli |
| contents | Efficiently solving NP-complete problems-such as protein structure prediction, cryptographic decryption, and vulnerability detection-remains a central challenge in computer science. Traditional electronic computers, constrained by the Turing machine's one-dimensional data processing and sequential operations, struggle to address these issues effectively. To overcome this bottleneck, computational models must adopt multidimensional data structures and parallel information processing mechanisms. Building on our team's proposed probe machine model (a non-Turing computational framework), this study develops a blocking probe technique that leverages DNA computing's inherent parallelism to identify all valid solutions for NP-complete problems in a single probe operation. Using the 27-vertex 3-coloring problem as a case study, we successfully retrieved all solutions through DNA molecular probe experiments. This breakthrough demonstrates the first implementation of a fully parallel computing system at the molecular level, offering a novel paradigm for tackling computational complexity. Our results indicate that the probe machine, with its parallel architecture and molecular implementation, transcends the limitations of classical models and holds promise for solving intricate real-world problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12470 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | DNA Probe Computing System for Solving NP-Complete Problems Xu, Jin Shi, XiaoLong Chen, Xin Wang, Fang Li, Sirui Ye, Pali Zhang, Boliang Deng, Di Kou, Zheng Qiang, Xiaoli Data Structures and Algorithms Efficiently solving NP-complete problems-such as protein structure prediction, cryptographic decryption, and vulnerability detection-remains a central challenge in computer science. Traditional electronic computers, constrained by the Turing machine's one-dimensional data processing and sequential operations, struggle to address these issues effectively. To overcome this bottleneck, computational models must adopt multidimensional data structures and parallel information processing mechanisms. Building on our team's proposed probe machine model (a non-Turing computational framework), this study develops a blocking probe technique that leverages DNA computing's inherent parallelism to identify all valid solutions for NP-complete problems in a single probe operation. Using the 27-vertex 3-coloring problem as a case study, we successfully retrieved all solutions through DNA molecular probe experiments. This breakthrough demonstrates the first implementation of a fully parallel computing system at the molecular level, offering a novel paradigm for tackling computational complexity. Our results indicate that the probe machine, with its parallel architecture and molecular implementation, transcends the limitations of classical models and holds promise for solving intricate real-world problems. |
| title | DNA Probe Computing System for Solving NP-Complete Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.12470 |