A new algorithm design technique for hard problems

DOI10.1016/J.TCS.2020.03.012MaRDI QIDQ2173301zbMATH OpenOpenAlexFDO

Authors Rupei Xu, Andras Farago

Publication date 22 April 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.03.012

zbMATH Keywords

errorless heuristicsNP-completenesspaddable language

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) General topics in the theory of algorithms (68W01) Analysis of algorithms (68W40)

Review text

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.

Recommendations

• A new algorithm design technique for hard problems, building on methods of complexity theory
• A result on the computational complexity of heuristic estimates for the A^* algorithm
• scientific article; zbMATH DE number 1566497
• scientific article; zbMATH DE number 3902037
• Algorithms and Data Structures

Cites work

• Almost every set in exponential time is P-bi-immune
• Average Case Complete Problems
• Bi-immune sets for complexity classes
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 1860654 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• On Isomorphisms and Density of NP and Other Complete Sets
• On Languages Accepted in Polynomial Time
• Paths in graphs
• Strong self-reducibility precludes strong immunity

Cited in

(3)

• scientific article; zbMATH DE number 458893 (Why is no real title available?)
• Improving Saddleback Search: A Lesson in Algorithm Design
• A new algorithm design technique for hard problems, building on methods of complexity theory

This page was built for publication: A new algorithm design technique for hard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2173301)