Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time

DOI10.1145/3154456zbMath1407.68199OpenAlexW2793462183MaRDI QIDQ4608731

Erkal Selman, Wied Pakusa, Svenja Schalthöfer

Publication date: 22 March 2018

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2016/6559/

zbMATH Keywords

finite model theorydescriptive complexitychoiceless polynomial timelogic for PTIMECai-Fürer-Immerman

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

This page was built for publication: Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time