Computer Science – Data Structures and Algorithms
Scientific paper
1999-03-16
Cybernetics and Systems Analysis. Vol. 33, 5(1997) pp. 635-640
Computer Science
Data Structures and Algorithms
10 pages, 2 figures
Scientific paper
The objective of this article is to formalize the definition of NP problems. We construct a mathematical model of discrete problems as independence systems with weighted elements. We introduce two auxiliary sets that characterize the solution of the problem: the adjoint set, which contains the elements from the original set none of which can be adjoined to the already chosen solution elements; and the residual set, in which every element can be adjoined to previously chosen solution elements. In a problem without lookahead, every adjoint set can be generated by the solution algorithm effectively, in polynomial time. The main result of the study is the assertion that the NP class is identical with the class of problems without lookahead. Hence it follows that if we fail to find an effective (polynomial-time) solution algorithm for a given problem, then we need to look for an alternative formulation of the problem in set of problems without lookahead.
No associations
LandOfFree
Formalization of the class of problems solvable by a nondeterministic Turing machine does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Formalization of the class of problems solvable by a nondeterministic Turing machine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Formalization of the class of problems solvable by a nondeterministic Turing machine will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-538284