die erste Aussage ist äquivalent zu: lim(n->inf) f / f ist endlich. Gilt das für alle Funktionen??
die zweite Aussage erhältst du aus dem Platzhierarchiesatz: Wir wissen, dass es Sprachen in PSPACE, aber außerhalb von LOGSPACE gibt. Was würde passieren, wenn die Aussage falsch wäre?
die dritte Aussage behauptet, dass Reduktion symmetrisch ist. Nimm hier mal eine Sprache aus P und eine EXP-vollständige Sprache. Hier kann man beweisen, dass man in eine Richtung auf jeden Fall reduzieren kann, und dass man in die andere Richtung nicht reduzieren kann.
Hilft dir das weiter?
*hust*
...ist doch ziemlich endlich, denke ich. Lass dich von der Schreibweise nicht verwirren.
Ein Pfad über mehrere Knoten, wobei Anfangs und Endknoten gleich sind
Ok, quasi ein Hamiltonkreis von s nach t nur innerhalb eines Teilgraphen.
Nun noch eine Frage dazu. Es steht . Ist also auch ein Kreis der Länge 1 erlaubt?
die zweite Aussage erhältst du aus dem Platzhierarchiesatz: Wir wissen, dass es Sprachen in PSPACE, aber außerhalb von LOGSPACE gibt. Was würde passieren, wenn die Aussage falsch wäre?
Würde P=NP gelten?
das heißt jeder Knoten, der nicht frei steht, ist Teil eines Zyklus ?
Source code |
|
1 2 3 |
a - b - c | / d - e |
This post has been edited 1 times, last edit by "Arne" (Sep 5th 2014, 2:40pm)