A new algorithm design technique for hard problems

DOI10.1016/J.TCS.2020.03.012zbMATH Open1448.68464OpenAlexW3012999633MaRDI QIDQ2173301FDOQ2173301

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

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

zbMATH Keywords

NP-completenesserrorless heuristicspaddable language

Mathematics Subject Classification ID

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

Cites Work

• Paths in graphs
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Average Case Complete Problems
• Almost every set in exponential time is P-bi-immune
• Bi-immune sets for complexity classes
• Title not available (Why is that?)
• On Languages Accepted in Polynomial Time
• Strong self-reducibility precludes strong immunity

Cited In (3)

• Improving Saddleback Search: A Lesson in Algorithm Design
• Title not available (Why is that?)
• 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)