A new algorithm design technique for hard problems (Q2173301)

This article presents a new measure for assessing heuristic algorithms, which considers the possibility that the algorithm does not produce any decision at all, in addition to the possibility of producing an suboptimal one. The first two sections present the background notations and definitions, including errorless heuristics, failure rate, roughly polynomial time and paddable language. The main result of the paper follows next, which considers the roughly polynomial time of paddable languages. The article concludes with a proposal for design of algorithms which uses the proof of the main result and a discussion of complexity.