Das deutsche Python-Forum

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

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.

cofi hat geschrieben: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