Can I read A Polynomial-Time Deterministic Algorithm for An NP-Complete Problem on EtoBox?

A Polynomial-Time Deterministic Algorithm for An NP-Complete Problem by Jiang, Xinwen; Wool, Holden is a scholarly article available to read on EtoBox.

What is A Polynomial-Time Deterministic Algorithm for An NP-Complete Problem about?

An NP-complete graph decision problem, the "Multi-stage graph Simple Path" (abbr. MSP) problem, is introduced. The problem is about the decision of 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 poly-time graph algorithm and the proof of its correctness. Our result implies NP$=$P, and hence no chance is left for NP$\neq$P any more. The algorithm exploits the data structure of reachable-path edge-set $R(e)$. By establishing the inter-play between preceding decisions and subsequent decisions, the computed (in a monotonically decreasing manner) information for $R(e)$ carries all necessary contextual information, and can be utilized to summarize the "history" and to detect the "future" for searching "global paths". Paths are always regarded as a collection of edge sets, for the avoidance of exponential complexity. Our proof of the algorithm builds upon a mathematical inductive 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\

Author

Jiang, Xinwen; Wool, Holden

Published

2021

Language

EN