Craig Alan Feinstein's Evidence That P ≠ NP: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
Title: 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 | 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 | 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/ | Link to Article: https://arxiv.org/abs/0310060v3 | ||
Authors: | Authors: | ||
arXiv ID: | arXiv ID: 0310060v3 | ||
[[Category:Computer Science]] | [[Category:Computer Science]] | ||
[[Category:Time]] | [[Category:Time]] | ||
[[Category:Be]] | |||
[[Category:Algorithm]] | [[Category:Algorithm]] | ||
[[Category:Can]] | [[Category:Can]] | ||
[[Category: | [[Category:Feinstein]] | ||
Revision as of 14:47, 24 December 2023
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