Automatische Schlagwort extraktion aus Texten = NP-Vollständ

[microkernel]

Moin

Ich soll als Hausaufgabe über die Ferien die Frage beantworten, warum eine autonome Schlagwort Extraktion aus Texten (Terminology extraction) NP-Vollständig oder NP-Schwer ist. Der Wikipedia Eintrag hilft mir da leider nicht groß weiter :/ Muss keine Doktorarbeit sein, nur eins zwei Sätze.
Kann mir da vielleicht jemand weiterhelfen?


Viele Grüße,
microkernel

[cofi]

Ich hab keine Ahnung von NLP und kann dir an der Front nicht helfen. Die meist genutzte Technik, um NP-completeness zu zeigen ist wohl die Reduktion auf ein anderes NP-complete Problem.

Wenn der "Beweis" auch sehr informal sein darf, koenntest du zeigen, dass es sehr aufwendig ist (eben O(x^n)) Schlagwoerter zu extrahieren, aber das Bestaetigen von Schlagwoertern aber einfach ist.

[EyDu]

Ich hab keine Ahnung von NLP und kann dir an der Front nicht helfen. Die meist genutzte Technik, um NP-completeness zu zeigen ist wohl die Reduktion auf ein anderes NP-complete Problem.

Der Beweis funktioniert besser, wenn man das bereits bekannte NP-vollständige Problem auf das vorhandene reduziert