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
Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries - MaRDI portal

Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries

From MaRDI portal

Publication:5317200

Jump to:navigation, search

DOI10.1137/S0097539701391002zbMath1082.68035MaRDI QIDQ5317200

Edith Hemaspaandra, Hemaspaandra, Lane A., Harald Hempel

Publication date: 16 September 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

Boolean hierarchy polynomial hierarchy computational complexity theory downward collapse downward translation of equality no-search easy-hard technique upward separation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

The 1-Versus-2 Queries Problem Revisited ⋮ The 1-versus-2 queries problem revisited

This page was built for publication: Extending Downward Collapse from 1-versus-2 Queries tom-versus-m+ 1 Queries

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