Hard instances of algorithms and proof systems

DOI10.1007/978-3-642-30870-3_13MaRDI QIDQ5891700zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum, Moritz Müller

Publication date 14 August 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://ddd.uab.cat/record/77023

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Hard instances of algorithms and proof systems
• scientific article; zbMATH DE number 1500525
• On the computational complexity of finding hard tautologies
• scientific article; zbMATH DE number 4001485
• scientific article; zbMATH DE number 1342213

Cited in

(11)

• Hardness assumptions in the foundations of theoretical computer science
• scientific article; zbMATH DE number 4095440 (Why is no real title available?)
• On an optimal randomized acceptor for graph nonisomorphism
• scientific article; zbMATH DE number 1304339 (Why is no real title available?)
• scientific article; zbMATH DE number 512976 (Why is no real title available?)
• scientific article; zbMATH DE number 1500525 (Why is no real title available?)
• scientific article; zbMATH DE number 4001485 (Why is no real title available?)
• scientific article; zbMATH DE number 7278086 (Why is no real title available?)
• From almost optimal algorithms to logics for complexity classes via listings and a halting problem
• Hard instances of algorithms and proof systems
• Automating algebraic proof systems is NP-hard

This page was built for publication: Hard instances of algorithms and proof systems

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