Craig Alan Feinstein's Evidence That P ≠ NP

Title: Craig Alan Feinstein's Evidence That P ≠ NP

Abstract: Craig Alan Feinstein, a researcher in computer science, presented evidence that the classes of decision problems that can be solved by deterministic polynomial-time algorithms (P) and nondeterministic polynomial-time algorithms (NP) are not equal. He focused on the SUBSET-SUM problem and proposed an algorithm (algorithm A) that could solve this problem in O(2n^2) time, assuming constant-time arithmetic and linear-time sorting. Feinstein argued that algorithm A had the best running-time for large problems and could be improved further by sorting sets S- ∪ (S- + an+1) and S+ instead of sorting sets S- and S+, reducing the running-time to 8 units of time. This improved strategy was shown to be more efficient than other methods, providing evidence that P ≠ NP.

Main Research Question: Is P = NP?

Methodology: Feinstein focused on the SUBSET-SUM problem, a well-known NP problem. He proposed an algorithm (algorithm A) that could solve this problem in O(2n^2) time. He then argued that algorithm A had the best running-time for large problems and could be improved further by sorting sets S- ∪ (S- + an+1) and S+ instead of sorting sets S- and S+, reducing the running-time to 8 units of time.

Results: Feinstein presented an algorithm (algorithm A) that could solve the SUBSET-SUM problem in O(2n^2) time. He argued that this algorithm had the best running-time for large problems and could be improved further by sorting sets S- ∪ (S- + an+1) and S+ instead of sorting sets S- and S+, reducing the running-time to 8 units of time.

Implications: Feinstein's evidence suggests that P ≠ NP. His improved algorithm for the SUBSET-SUM problem shows that it is possible to solve NP problems more efficiently than previously thought, providing new insights into the P vs. NP problem.

Link to Article: https://arxiv.org/abs/0310060v6 Authors: arXiv ID: 0310060v6