Theoretische informatik

Wissenschaft Informatik
#1

Hi Leute,

wir haben die Komplexitätsklasse NP wie folgt definiert:
„ein Problem ist genau dann in NP, wenn es ein Zertifikat polynomialer Länge gibt, dass in Polynomialzeit kontrolliert werden kann.“

Leider verstehe ich nicht so gnz, wieso das Zertifikat eine polynomiale Länge haben muss. Warum ist das so wichtig? Was ist, wenn dieser Fall nicht gegeben wäre?

Was mir wahrscheinlich sehr helfen würde, wäre ein Beispiel eines Zertifikates, welches nicht polynomial lang ist.
Hast du vllt. eins oder kannst mir mit anderen Worten erklären, wie man diese Definition zu verstehen hat? Wäre echt supi von dir. :smile:

Mit freundlichen Grüßen

Clodan

#2

Hallo Clodan,

bei mir ist es fast 10 Jahre her, dass ich mich mit dem Thema beschäftigt habe und damals ist mir die Zertifikatsdefinition auch nur kurz begegnet. Was aber immer auffällig ist: viele Informatiker haben Probleme mit „dass“ und „das“, obwohl man doch meinen sollte, dass gerade die ein Auge dafür haben müssten…
Zu Deiner Frage:
Die Zertifikatsdefinition verlang auch, dass das Zertifikat polynomiell ist, weil es sonst ja sein könnte, dass wir nicht mehr in NP liegen, sondern z.B. sogar in EXPTIME, sofern NP =/= EXPTIME.
Das Zertifikat wird auch „Zeuge“ genannt. Darunter kann man sich z.B. eine Belegung für eine aussagenlogische Formel vorstellen.
Falls Du andere Antworten erhalten hast, würden die mich interessieren!

beste Grüße
Nne

#3

Hallo Clodan,

leider kenne ich die Definition über Zertifikate nicht. Ich weiß in dem Zusammenhang nicht einmal, wie Zertifikat definiert ist. Daher kann ich dir nicht wirklich weiterhelfen, sorry.

Was auch immer ein Zertifikat ist, hätte es mehr als polynomiale Länge, könntest du es dir in der Zeit nicht mal komplett anschauen!

gruss, mofte