Monadic NP and built-in trees

DOI10.1007/3-540-63172-0_44MaRDI QIDQ4362922zbMATH OpenFDO

Authors Martin Kreidler, Detlef Seese

Publication date 10 May 1998

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

Full work available at URL https://doi.org/10.1007/3-540-63172-0_44

zbMATH Keywords

descriptive complexityEhrenfeucht-Fraïssé gamesfinite model theorygraph connectivityMonadic Second-Order Logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Monadic NP and graph minors
• Graph connectivity, monadic NP and built-in relations of moderate degree
• On monadic NP vs monadic co-NP

Cited in

(4)

• On monadic NP vs monadic co-NP
• Reachability is harder for directed than for undirected finite graphs
• Monadic NP and graph minors
• Graph connectivity, monadic NP and built-in relations of moderate degree

This page was built for publication: Monadic NP and built-in trees

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