Welche der folgenden Aussagen sind wahr?

Question

Accepted Answer

Jede PSPACE-vollständige Sprache ist coNP-schwer.

Accepted Answer

Jede PSPACE-vollständige Sprache ist NP-schwer.

Accepted Answer

PSPACE ist die Klasse aller Sprachen, die von deterministischen Turing-Maschinen mit polynomiellen Platzbedarf entschieden werden können.

Answer

PSPACE ist die Klasse aller Sprachen, die Spiele mit 2 Spielern kodieren.

Answer

Jede NP-schwere Sprache ist PSPACE-vollständig.

Answer

TQBF ist PSPACE-schwer, aber nicht in PSPACE.

Crowdly