You are not logged in.

Leela

Mädchen

  • "Leela" is female
  • "Leela" started this thread

Posts: 88

Date of registration: Sep 15th 2011

1

Thursday, September 4th 2014, 12:39pm

KvA - Aussagen

Hallo!

Für folgende 3 Aussagen kann ich nicht sagen, ob richtig oder falsch. Könnte mir die vielleicht jemand erklären?



lg
Doro

nano

Alter Hase

  • "nano" is male

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

2

Thursday, September 4th 2014, 1:32pm

Hallo Doro,

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?

nano

Alter Hase

  • "nano" is male

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

3

Thursday, September 4th 2014, 1:35pm

Achja, in der Übung hatten wir auch noch die Sprachen "leere Menge" und Σ*. Man kann von diesen Sprachen auf alle anderen reduzieren, man kann aber keine andere Sprache auf die leere Menge oder Σ* reduzieren.

barhoum

Praktikant

Posts: 26

Date of registration: Dec 13th 2010

4

Thursday, September 4th 2014, 4:15pm

Hallo,


hat Jemand eine Lösung zu dieser Aufgabe ?

Leela

Mädchen

  • "Leela" is female
  • "Leela" started this thread

Posts: 88

Date of registration: Sep 15th 2011

5

Thursday, September 4th 2014, 4:31pm

Hallo nano,

die erste Aussage ist äquivalent zu: lim(n->inf) f / f ist endlich. Gilt das für alle Funktionen??

Nein, gilt natürlich nicht.

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?

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?

Ok. Danke

lg Doro

bommy

Praktikant

Posts: 9

Date of registration: Oct 5th 2012

6

Thursday, September 4th 2014, 6:19pm

*hust*



...ist doch ziemlich endlich, denke ich. Lass dich von der Schreibweise nicht verwirren. :)

  • "Julian" is male

Posts: 66

Date of registration: Oct 4th 2006

Location: Lehrte

7

Thursday, September 4th 2014, 7:43pm

Mein Kommentar hat sich erledigt. Könnte gelöscht werden.

This post has been edited 2 times, last edit by "Julian" (Sep 4th 2014, 7:45pm)


bommy

Praktikant

Posts: 9

Date of registration: Oct 5th 2012

8

Thursday, September 4th 2014, 7:51pm

Wegen Punkt 1.

Ich glaube ihr verwechselt klein o und groß O Notation. Klein o wird über den Limes definiert und groß O über eine Ungleichung.

und


Gibt also für beide Varianten eine Limes-Variante. :)

This post has been edited 1 times, last edit by "bommy" (Sep 4th 2014, 9:16pm)


  • "Julian" is male

Posts: 66

Date of registration: Oct 4th 2006

Location: Lehrte

9

Thursday, September 4th 2014, 8:34pm

Genau aus dem Grund hab ich den Kommentar weg genommen, weil ich mich verlesen hatte ;) Das kleiner unendlich übersehen.

SammysHP

Forenwolf

  • "SammysHP" is male

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

10

Thursday, September 4th 2014, 8:41pm

Aber dafür hat die Nachwelt jetzt eine schöne Erklärung. ;)

Leela

Mädchen

  • "Leela" is female
  • "Leela" started this thread

Posts: 88

Date of registration: Sep 15th 2011

11

Friday, September 5th 2014, 8:30am

*hust*



...ist doch ziemlich endlich, denke ich. Lass dich von der Schreibweise nicht verwirren. :)

:love: Upsi! Also ist die Aussage korrekt, richtig?

Nun habe ich noch eine Frage zu der Aufgabe die barhoum gestellt hat. Ich verstehe die Zyklusdefinition nicht ganz. Was ist damit genau gemeint? Ist das einfach nur ein Pfad zwischen Knoten oder ein Kreis oder etwas ganz anderes?

SammysHP

Forenwolf

  • "SammysHP" is male

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

12

Friday, September 5th 2014, 9:04am

Ein Pfad über mehrere Knoten, wobei Anfangs und Endknoten gleich sind.

Leela

Mädchen

  • "Leela" is female
  • "Leela" started this thread

Posts: 88

Date of registration: Sep 15th 2011

13

Friday, September 5th 2014, 9:25am

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?

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

14

Friday, September 5th 2014, 9:34am

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?


Bei einem Hamilton'schen Kreis wird jeder Knoten im Graphen genau einmal besucht. Davon ist hier nicht die Rede. Ein Zyklus ist einfach ein Pfad von einem Knoten weg und wieder zurück zu ihm (um die Definition in der Aufgabe nochmal natürlich sprachlich zu wiederholen).
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

nano

Alter Hase

  • "nano" is male

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

15

Friday, September 5th 2014, 10:31am

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?


Unter anderem. Es wäre LOGSPACE = PSPACE und wegen LOGSPACE P NP PSPACE wäre auch P = NP.
Aber es reicht hier schon zu sagen, dass LOGSPACE = PSPACE durch den Platzhierarchiesatz nicht gelten kann.

barhoum

Praktikant

Posts: 26

Date of registration: Dec 13th 2010

16

Friday, September 5th 2014, 11:43am

das heißt jeder Knoten, der nicht frei steht, ist Teil eines Zyklus ?

This post has been edited 2 times, last edit by "barhoum" (Sep 5th 2014, 12:44pm)


barhoum

Praktikant

Posts: 26

Date of registration: Dec 13th 2010

17

Friday, September 5th 2014, 1:02pm

Beim Übungsblatt 9 Aufgabe 1 warum verbindet man nicht einfach s mit t, in dem Fall wo die Anzahl der Knoten gerade ist.

nano

Alter Hase

  • "nano" is male

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

18

Friday, September 5th 2014, 1:14pm

Damit würde man teilweise Even-Hamcircs erzeugen, obwohl im Graphen kein Hampath von s nach t war. Versuche da einmal, ein kleines Beispiel zu konstruieren.

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

19

Friday, September 5th 2014, 1:30pm

das heißt jeder Knoten, der nicht frei steht, ist Teil eines Zyklus ?


Nein. Beispiel:

Source code

1
2
3
a - b - c
    | /
    d - e


a und e sind nicht Teil eines Zyklus, b, c und d hingegen schon.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 1 times, last edit by "Arne" (Sep 5th 2014, 2:40pm)


SammysHP

Forenwolf

  • "SammysHP" is male

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

20

Friday, September 5th 2014, 2:33pm

Ich glaube, die Formatierung macht das Beispiel kaputt.