Abstract: Optimal solving of the NP-hard problems strongly motivates both the researchers and the practitioners to try to solve such problems heuristically, by making a trade-off between computational time and solution’s quality. Among the classes of heuristic methods for NP-hard problems, the polynomial approximation algorithms aim at solving a given NP-hard problem in polynomial time by computing feasible solutions that are, under some predefined criterion, as near to the optimal ones as possible. P is the class of decision problems that we can solve in polynomial time and NP is the class of problems for which we can check the solution in polynomial time. Visually, problems that are easy to solve are also problems that are easy to test. Therefore, P NP. In this paper, we propose an approach to the P vs NP question through a class of the most difficult problems among the problems in the NP class. Such problems are called NP-complete problems.
Keywords: NP class, NP-complete class, Karp, NP-hard problems, heuristics.
|
DOI:
10.17148/IJARCCE.2021.10909
