Theoretische Informatik Halteproblem etc.?
Fragen:
=> In welche Komplexitätsklasse fällt das Halteproblem?
Das Halteproblem ist unentscheidbar. Liegt es somit in NP-schwer oder in überhaupt einer Komplexitätsklasse?
Für Sprachen von Typ 3 und Typ 2 gilt, dass diese unter Vereinigung abgeschlossen sind. Was gilt dann für Typ 3 vereinigt mit Typ 2?
=> Ist diese Vereinigung dann auch abgeschlossen?
MFG
2 Antworten
Zeitkomplexitätsklassen geben obere Schranken für die asymptotisvhe Zeit an, die benötigt wird, um ein Problem zu entscheiden . Unentscheidbare Probleme liegen daher in keiner Komplexitätsklasse, da sie unter Umständen nie halten.
Natürlich können unentscheidbare Probleme auch nicht in begrenztem Platz entschieden werden und sind damit auch nicht in solchem Komplexitätsklassen (PSPACE etwa, da erzählt ChatGPT Blödsinn).
Ob man dennoch immer nur begrenzten Platz auf dem Band benötigt, um einen NEA für das Halteproblem zu bauen, ist eine andere Frage, die ich nicht beantworten kann.
Typ 3 ist echte Teilmenge von Typ 2. Typ 2 vereinigt Typ 3 ist also wieder Typ 2.
Gut, also NP-schwer ist tatsächlich eine AusnHme, da es durch keine obere Schranke der Laufzeit definiert ist, sondern nur dadurch, dass jedes Problem aus NP auf dieses in Poly-zeit rediziert werden kann, was beim Halteproblem der Fall ist. Es ist daher NP-schwer
Frage 1:
Das Halteproblem ist ein Entscheidungsproblem, das für jede Turingmaschine M und jede Eingabe w bestimmt, ob M bei Eingabe von w irgendwann haltet.
Es ist bekannt, dass das Halteproblem unentscheidbar ist. Das bedeutet, dass es keine Turingmaschine gibt, die das Halteproblem für alle Eingaben korrekt entscheidet.
Da das Halteproblem unentscheidbar ist, kann es nicht in einer Komplexitätsklasse liegen, die entscheidbar ist. Die Komplexitätsklassen P und NP sind beide entscheidbar, daher kann das Halteproblem nicht in diesen Klassen liegen !
Dafür gibt es aber auch Klassen.
Die Komplexitätsklasse PSPACE ist eine solche Klasse. PSPACE ist die Klasse aller Entscheidungsprobleme, die in polynomieller Zeit gelöst werden können, wobei der Speicherbedarf auch polynomiell ist. Schau dir mal PSPACE an.
Antwort:
Das Halteproblem ist unentscheidbar. Es ist nicht bekannt, ob es in einer Komplexitätsklasse liegt, die entscheidbar ist. Es ist jedoch möglich, dass es in der Komplexitätsklasse PSPACE liegt.
Frage 2:
Die Komplexitätsklasse NP-schwer ist die Klasse aller Probleme, die mindestens so schwer sind wie jedes Problem in NP.
Das Halteproblem ist unentscheidbar, daher ist es mindestens so schwer wie jedes Problem in NP. Das bedeutet, dass das Halteproblem in NP-schwer liegt, wenn NP-schwer nicht leer ist.
Wenn NP-schwer leer ist, dann liegt das Halteproblem in keiner Komplexitätsklasse.
Antwort:
Das Halteproblem ist mindestens so schwer wie jedes Problem in NP. Wenn NP-schwer nicht leer ist, dann liegt das Halteproblem in NP-schwer. Wenn NP-schwer leer ist, dann liegt das Halteproblem in keiner Komplexitätsklasse.
Frage 3:
Spricht man von Komplexitätsklassen von Sprachen, so sind diese unter Vereinigung abgeschlossen, wenn die Vereinigung zweier Sprachen aus der Klasse ebenfalls in der Klasse liegt.
Für Sprachen von Typ 3 und Typ 2 gilt, dass diese unter Vereinigung abgeschlossen sind. Das bedeutet, dass die Vereinigung zweier Sprachen von Typ 3 oder die Vereinigung zweier Sprachen von Typ 2 ebenfalls in Typ 3 oder Typ 2 liegt.
Für die Vereinigung von Sprachen von Typ 3 und Typ 2 gilt daher auch, dass diese unter Vereinigung abgeschlossen ist.
Antwort:
Die Vereinigung von Sprachen von Typ 3 und Typ 2 ist unter Vereinigung abgeschlossen. Das bedeutet, dass die Vereinigung zweier Sprachen von Typ 3 oder die Vereinigung zweier Sprachen von Typ 2 ebenfalls in Typ 3 oder Typ 2 liegt.
Nein !
Einfache Internetsuche hätte es auch getan mein Jung...
Ihr müsst mal lernen eigenständiger zu werden, gerade bei solchen Themen.
hier findest du deine Antworten;
Komplexitätsklassen — doku-project 1.0 documentation
trotzdem bitte
So ganz scheint das mit der Recherche nicht geklappt zu haben, zimindest beim Thema PSPACE.
Für Verweise auf irgendwelche Seiten gibt es bei mir kein "Danke sagen". Konkrete und erklärende Antworten, dafür schon.
Ich lese aus deiner Antwort, dass du folgern würdest, dass das Halteproblem somit "nicht" in NP-schwer liegt. Richtig?