On polynomial time computation over unordered structures

DOI10.2178/jsl/1190150152zbMath1020.03038arXivmath/0102059MaRDI QIDQ4779654

Saharon Shelah, Andreas Blass, Yuri Gurevich

Publication date: 6 October 2003

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0102059

zbMATH Keywords

bipartite graph; matching; counting; polynomial time; complexity classes; descriptive complexity theory; fixpoint logic

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

03D15: Complexity of computation (including implicit computational complexity)

68Q19: Descriptive complexity and finite models