Completeness for First-order Properties on Sparse Structures with Algorithmic Applications
Publication:4629991
DOI10.1145/3196275zbMath1454.68054OpenAlexW4235156957WikidataQ128708728 ScholiaQ128708728MaRDI QIDQ4629991
Russell Impagliazzo, Jiawei Gao, Antonina Kolokolova, R. Ryan Williams
Publication date: 28 March 2019
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3196275
Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01)
Related Items (6)
This page was built for publication: Completeness for First-order Properties on Sparse Structures with Algorithmic Applications