|
|
| 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
|
|
09.12.2015 20:28 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
 |
|
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 07:00 |
|
|
|
|
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 08:58 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Oh, entschuldigung. Zu schnell geschossen und nicht richtig gelesen.
Ich denke mit ![[latex]a^ib^ic^i[/latex]](http://www.matheboard.de/latex2png/latex2png.php?a^ib^ic^i) 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
|
|
|
10.12.2015 10:41 |
|
|
|
|
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 14:08 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Kurz und knapp: Ich denke ja, die Sprache dürfte in P liegen.
Gruß,
Karlito
|
|
|
10.12.2015 16:03 |
|
|
|
