ISSN:
1432-5217
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract This paper investigates the effectiveness of using finite improvement algorithms for solving decision, search, and optimization problems. Finite improvement algorithms operate in a finite number of iterations, each taking a polynomial amount of work, where strict improvement is required from iteration to iteration. The hardware, software, and way of measuring complexity found in the polynomial setting are modified to identify the concept of repetition and define the new classes of decision problems,FI andNFI. A firstNFI-complete problem is given using the idea ofFI-transformations. Results relating these new classes toP, NP, andNP-complete are given. It is shown that if an optimization problem in a new classPGS isNP-hard, thenNP=co-NP. TwoPGS problems are given for which no polynomial algorithms are known to exist.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01415994
