Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

$A \notin EXPTIME \backslash PSPACE$: Verständnisproblem

0 Punkte
57 Aufrufe
$A \notin EXPTIME \backslash PSPACE$

Soll heißen A ist nicht Element von EXPTIME ohne PSPACE?

Weil so wie ich die Aussage lese, mach sie für mich keinen Sinn. PSPACE is doch eine Teilmenge von EXPTIME und P und NP sind wiederum eine Teilmenge von PSPACE. Wenn ich jetzt PSPACE "entferne" ist damit nicht auch gleichzeitig A "weg", da es in PSPACHE liegt, da A NP-vollständig ist?

Oder Darf man sich das nicht so vorstellen, sondern praktisch im Gedanken nur den PSPACE-Kreis entfernen und die Kreise die darin waren stehen lassen? (also bildlich gesprochen)
Gefragt 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (167,990 Punkte)  
Bearbeitet 1, Dez 2014 von Lukas König

Eine Antwort

+1 Punkt
 
Beste Antwort

Das stimmt schon so, PSPACE ist Teilmenge von EXPTIME. Also ist EXPTIME\PSPACE nur noch die Menge um PSPACE herum (bis zur Grenze von EXPTIME). In dieser Menge ist also auch NP entfernt worden. Also ist A nicht mehr Teil der resultierenden Menge.

Philippe (Tutor)

Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
...