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 suggests the class of decision problems that can be solved by deterministic polynomial-time algorithms, P, is not equal to the class of decision problems that can be solved by nondeterministic polynomial-time algorithms, NP. He did this by examining the SUBSET-SUM problem and proposing an algorithm, algorithm A, that solves the problem in O(2n^2) time. Feinstein argued that algorithm A has the best running-time for large N and can be used to solve two subproblems independently, reducing the time complexity. His work suggests that there might be a more efficient way to solve the SUBSET-SUM problem, further supporting the idea that P ≠ NP.
Main Text:
Craig Alan Feinstein, a computer scientist, provided evidence that suggests the class of decision problems that can be solved by deterministic polynomial-time algorithms, P, is not equal to the class of decision problems that can be solved by nondeterministic polynomial-time algorithms, NP. He focused on the SUBSET-SUM problem, which involves determining whether there exists a vector with specific properties.
Feinstein proposed an algorithm, called algorithm A, that can solve the SUBSET-SUM problem in O(2n^2) time. This algorithm works by sorting two sets, b-S- and S+, in ascending order and comparing the first two elements in each list. If there is a match, the algorithm stops and outputs that there is a solution. If not, it compares the greater element with the next element on the other list and continues until there is a match or one of the lists runs out of elements.
Feinstein argued that algorithm A has the best running-time for large N and can be used to solve two subproblems independently. This reduces the time complexity and suggests that there might be a more efficient way to solve the SUBSET-SUM problem. His work supports the idea that P ≠ NP, as it provides evidence that the two classes are not equal.
Link to Article: https://arxiv.org/abs/0310060v3 Authors: arXiv ID: 0310060v3