Sei A eine Sprache (theoretische Informatik)

Question

Aufgabe:

Sei A eine Sprache. Ist das richtig?

Problem/Ansatz:

Hey wenn man davon ausgeht dass A eine Sprache ist, wäre es dann richtig zu sagen: ist A NP-vollständig und A ૯ NP, so gilt P ungleich NP. Oder P = NP?

Answer 1

ist A NP-vollständig

Dann ist A ∈ NP laut Definition von NP-vollständig.

so gilt P ungleich NP

Es ist P ⊆ NP. Aus der Tatsache, dass A ∈ NP ist, lässt sich deshalb weder schlussfolgern, dass A ∈ P ist, noch dass A ∉ P ist.