Craig Alan Feinstein's Evidence That P ≠ NP

From Simple Sci Wiki
Revision as of 14:47, 24 December 2023 by SatoshiNakamoto (talk | contribs)
Jump to navigation Jump to search

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