Sprachen die (nicht) in NP liegen

Question

Hallo,

ich bin auf der Suche nach:

1. Sprachen die in NP liegen?

(Hierzu würde ich 3Sat sagen da sich SAT auf 3SAT in polynomieller Zeit reduzieren lässt)

2. Sprachen die nicht in NP liegen?

Habe ich leider noch keine Ansatz.

Könnte mir jemand tipps geben?

Comments

"universität" und "komplex" sind etwas unpräzise Tags.

Wenn jemand die gleiche Frage hat, findet er so deine Frage via Suche kaum.

Nur für den Fall, dass jemand antworten kann, wäre es nicht schlecht, wenn du noch präzisere Tags nachliefern könntest.

---

Würde ich seeehr gern allerdings kommt dann immer die Meldung das ich 500 Punkte? brauche um selber tags zu erstellen :)

---

Ich kann die oben für dich einfügen, wenn du mir die als Kommentar hinschreibst.

---

Ja bitte :)

Berechenbarkeitstheorie

TheoretischeInformatik

Komplexitätstheorie

Mathematik

Answer 1

3SAT und CLIQUE liegen beispielsweise in NP. Beachte, dass P eine Teilmenge von NP ist, möglicherweise sind sogar beide Klassen gleich (P-NP-Problem).

Das Halteproblem liegt nicht in NP, ist so weit ich weiß jedoch NP-schwer. Und das obwohl es nicht mal entscheidbar ist. Verrückte Welt.

Comments

Hey das mit 3Sat leuchtet mir ein!
Aber wie kann ich begründen das das halteproblem nicht in NP ist?

---

Hm bin mit dem Thema nicht soo sehr vertraut, aber im Prinzip liegt ein Problem ja in NP, wenn man bei einer gegebenen Lösung des Problems in polynomieller Zeit entscheiden kann, ob die Lösung korrekt ist. Und das gestaltet sich bei dem Halteproblem nun mal als vergleichsweise schwierig.