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 can solve it in O(2n^2) time, assuming constant-time arithmetic and linear-time sorting. Feinstein argued that algorithm A has the best running-time for large N and proved this through induction. He also proposed an improved strategy that further reduces the running-time.

Main Research Question: Is P = NP?

Methodology: Feinstein focused on the SUBSET-SUM problem and proposed an algorithm (algorithm A) that can solve it in O(2n^2) time. He used induction to prove that algorithm A has the best running-time for large N.

Results: Feinstein argued that algorithm A has the best running-time (with respect to n for large N) of all algorithms that solve the SUBSET-SUM problem, assuming constant-time arithmetic and linear-time sorting. He also proposed an improved strategy that further reduces the running-time.

Implications: Feinstein's evidence suggests that P ≠ NP, as his algorithm can solve the SUBSET-SUM problem more efficiently than any other known algorithm. This could potentially lead to new algorithms and approaches in computer science and could have implications in other fields that rely on decision problems.

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