0 Daumen
141 Aufrufe

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?

Avatar von

1 Antwort

0 Daumen
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.

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community