A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916896689881088 |
|---|---|
| author | Jiang, Xinwen Wool, Holden |
| author_facet | Jiang, Xinwen Wool, Holden |
| contents | We introduce an NP-complete graph decision problem, the "Multi-stage graph Simple Path" (abbr. MSP) problem, which focuses on determining the existence of specific "global paths" in a graph $G$. We show that the MSP problem can be solved in polynomial ($O(|E|^9)$) time, by proposing a polynomial-time graph algorithm and the proof of its correctness. Our result implies NP$=$P. The algorithm leverages the data structure of reachable-path edge-set $R(e)$. By establishing the interplay between preceding decisions and subsequent decisions, the information computed for $R(e)$ (in a monotonically decreasing manner) carries all necessary contextual information, and can be utilized to summarize the "history" and to detect the "future" for searching "global paths". The relation of $R(e)$ of different stages in the multi-stage graph resembles the state-transition equation in dynamic programming, though it is much more convoluted. To avoid exponential complexity, paths are always treated as a collection of edge sets. Our proof of the algorithm is built upon a mathematical induction - based proving framework, which relies on a crucial structural property of the MSP problem: all MSP instances are arranged into the sequence {$G_0,G_1,G_2,...$}, and each $G_{j}(j>0)$ in the sequence must have some $G_{i}(0\leq i<j)$ that is completely consistent with $G_{j}$ on the existence of "global paths". As an auxiliary method, we have conducted tests using multiple AI systems. With the help of a suggested query list that covers the entire content of the paper, the paper has been verified by Doubao, DeepSeek, Kimi, iFlytek Spark, ERNIE Bot, Gemini, and GPT. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_03877 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem Jiang, Xinwen Wool, Holden Data Structures and Algorithms 68XX, 68Q05 F.2 We introduce an NP-complete graph decision problem, the "Multi-stage graph Simple Path" (abbr. MSP) problem, which focuses on determining the existence of specific "global paths" in a graph $G$. We show that the MSP problem can be solved in polynomial ($O(|E|^9)$) time, by proposing a polynomial-time graph algorithm and the proof of its correctness. Our result implies NP$=$P. The algorithm leverages the data structure of reachable-path edge-set $R(e)$. By establishing the interplay between preceding decisions and subsequent decisions, the information computed for $R(e)$ (in a monotonically decreasing manner) carries all necessary contextual information, and can be utilized to summarize the "history" and to detect the "future" for searching "global paths". The relation of $R(e)$ of different stages in the multi-stage graph resembles the state-transition equation in dynamic programming, though it is much more convoluted. To avoid exponential complexity, paths are always treated as a collection of edge sets. Our proof of the algorithm is built upon a mathematical induction - based proving framework, which relies on a crucial structural property of the MSP problem: all MSP instances are arranged into the sequence {$G_0,G_1,G_2,...$}, and each $G_{j}(j>0)$ in the sequence must have some $G_{i}(0\leq i<j)$ that is completely consistent with $G_{j}$ on the existence of "global paths". As an auxiliary method, we have conducted tests using multiple AI systems. With the help of a suggested query list that covers the entire content of the paper, the paper has been verified by Doubao, DeepSeek, Kimi, iFlytek Spark, ERNIE Bot, Gemini, and GPT. |
| title | A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem |
| topic | Data Structures and Algorithms 68XX, 68Q05 F.2 |
| url | https://arxiv.org/abs/2108.03877 |