A new algorithm design technique for hard problems

DOI10.1016/j.tcs.2020.03.012zbMath1448.68464OpenAlexW3012999633MaRDI QIDQ2173301

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

NP-completenesserrorless heuristicspaddable language

Mathematics Subject Classification ID

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

Cites Work

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

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