On a logical approach to estimating computational complexity of potentially intractable problems.

DOI10.1007/B11926MaRDI QIDQ5900817zbMATH OpenOpenAlexFDO

Authors Andrzej Szałas

Publication date 20 April 2010

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

Full work available at URL https://doi.org/10.1007/b11926

zbMATH Keywords

descriptive complexitysecond-order logicsecond-order quantifier eliminationtransversal hypergraph problem

Mathematics Subject Classification ID

Hypergraphs (05C65) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1931696
• Achieving new upper bounds for the hypergraph duality problem through logic
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• scientific article; zbMATH DE number 1670855
• Achieving new upper bounds for the hypergraph duality problem through logic

Cited in

(1)

• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems

This page was built for publication: On a logical approach to estimating computational complexity of potentially intractable problems.

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