Die Komplexitätsklasse [B]P[/B]

09.12.2015, 20:28	Auf diesen Beitrag antworten »
Daniel Informatik	Die Komplexitätsklasse [B]P[/B] Hallo zusammen, Ich habe da mal eine Frage zur Komplexitätsklasse P. Ich finde im Internet nur Probleme, wie SAT, Circuit Value Problem, die dieser zugeordnet sind. Jedoch hätte ich gerne eine Sprache die in P liegt und nicht in der Form eines Problems wie SAT ist. Eher eine Sprache, wie sie in der Klasse der kontextsensitiven Sprachen z.B. (a^i)(b^i)(c^i) ist. Kann man eine derartige Sprache angeben die in P liegt. Oder bezieht sich P nur auf Probleme? Ich dachte eigentlich dass ein Problem und eine Sprache eigentlich dasselbe wären. Das Problem soll jedoch nicht in tieferen Sprachklassen liegen. Also nicht in der Klasse der kontextfreien Sprachen. Vielen Dank für eure Hilfe, Gruß Daniel


10.12.2015, 07:00	Auf diesen Beitrag antworten »
Karlito	Hallo Daniel, der CYK-Algorithmus ist kubisch und dient zur Erkennung kontextfreier Sprachen. Es werden von Compilern effektivere Algorthmen verwendet, meines Wissens nach, bleiben diese jedoch polynomiell. Gruß, Karlito
10.12.2015, 08:58	Auf diesen Beitrag antworten »
Daniel Informatik	Hallo Karlito, vielen Dank für deine schnelle Antwort. Mit dem CYK-Algotithmus kann ich kontextfreie Sprachen erkennen. Ich hätte jedoch gerne ein Beispiel für eine Sprache, die nicht in der Klasse der kontextfreien Sprachen, jedoch in P liegt. Also ich brauche eher ein Problem/Sprache als ein Algorithmus für die Erkennung des Problems. Daniel
10.12.2015, 10:41	Auf diesen Beitrag antworten »
Karlito	Oh, entschuldigung. Zu schnell geschossen und nicht richtig gelesen. Ich denke mit liegst Du schon gar nicht so schlecht. Kontextsensitive Sprachen können von einer linear beschränkten Turingmaschine erkannt werden. Jetzt ist die Frage, wie ein entsprechendes Programm aussähe. Andrererseits ist das Problem, dass man viele Probleme schneller Lösen kann, wenn man den Platzbedarf erhöht. Mit entsprechend großen Vektorregistern kann man theroetisch auch Matrizen in linearer Zeit Multiplizieren. Ich befürchte die Frage lässt sich nur beantworten, wenn man einige Randbedingungen festlegt. Zuzmindest braucht es wohl eine Platzbeschränkung. Gruß, Karlito
Anzeige

10.12.2015, 14:08	Auf diesen Beitrag antworten »
Daniel Informatik	Hallo Karlito, Ist diese kontextsensitive Sprache denn auch ein Element welches in P liegt. Oder handelt es sich dabei nur um eine Sprache, die in NP liegt, oder ist sie vielleicht sogar ausserhalb von NP? Mir geht es persöhnlich eher nicht um das Lösen des Problems oder irgendwelche Programme, die jenes lösen. Ich frage mich eigentlich nur, ob es "einfache" Probleme/Sprachen, in der Art a^i b^i ... gibt, die der Klasse P angehören. Oder muss man um ein Problem der Klasse P zu beschreiben "weit ausholen" und so etwas wie 2SAT bauen, um ein Problem der Klasse P zu bekommen? Wie die Lösung des Problems aussieht ist mir wirklich egal. Es geht nur um die Definition vom Problem selbst. Vielen Dank für deine Unterstützung, Gruß Daniel
10.12.2015, 16:03	Auf diesen Beitrag antworten »
Karlito	Kurz und knapp: Ich denke ja, die Sprache dürfte in P liegen. Gruß, Karlito

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »