Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Comparing the Power of Games on Graphs - MaRDI portal

Comparing the Power of Games on Graphs

From MaRDI portal

Publication:4366126

Jump to:navigation, search

DOI10.1002/malq.19970430402zbMath0888.03027OpenAlexW2171521913MaRDI QIDQ4366126

Ronald Fagin

Publication date: 10 May 1998

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19970430402

zbMATH Keywords

computational complexity Ehrenfeucht-Fraïssé game descriptive complexity Ajtai-Fagin game monadic NP

Mathematics Subject Classification ID

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

Related Items (3)

Comparing the power of monadic NP games ⋮ Verifiable properties of database transactions ⋮ The closure of monadic NP

Cites Work

This page was built for publication: Comparing the Power of Games on Graphs

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:4366126&oldid=18363575"