Fragen mit komplexität-Tag

0 Pluspunkte 0 Minuspunkte

0 Antworten

447 Aufrufe

Entscheidbarkeit, Semientscheidbarkeit und Nichtentscheidbarkeit

Gefragt 10, Feb 2019 in BER-AA von uzmzu uzmzu Lernwillige(r) (260 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

187 Aufrufe

Entscheidbar und NP-Schwer Polynomialreduzierbarkeit

Gefragt 7, Feb 2019 in BER-AH von ucsyc ucsyc Lernwillige(r) (570 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

176 Aufrufe

dies ist ein test

Gefragt 18, Jun 2018 in BER-AA von Dozent (10.1m Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

246 Aufrufe

Fehlende Lösung (Aufgabe 5 - Nachklausur 2013)

Gefragt 12, Jan 2018 in 2013-N-05 von Anonym

1 Pluspunkt 0 Minuspunkte

1 Antwort

365 Aufrufe

Polynomialzeitreduktion und Komplexitätsklasse

Gefragt 15, Okt 2017 in BER-AA von uqdme uqdme Lernwillige(r) (250 Punkte)

0 Pluspunkte 0 Minuspunkte

0 Antworten

70 Aufrufe

2017 Nachklausur, Aufgabe 5

Gefragt 13, Okt 2017 in Aufgabenübersicht von Sebastian Bergdolt Lernwillige(r) (770 Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

95 Aufrufe

Kann ein Problem X aus P auch NP-schwer sein ?

Gefragt 17, Jul 2017 in BER-AL von Anonym

0 Pluspunkte 0 Minuspunkte

2 Antworten

160 Aufrufe

Diagonalsprache = Komplement?

Gefragt 12, Feb 2017 in Kapitel 7 von ugewo ugewo Lernwillige(r) (290 Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

150 Aufrufe

Kontrollfrage 3 Kpt. 7 Infobuch - Reduzierbarkeit

Gefragt 7, Feb 2017 in Kapitel 7 von Anonym

1 Pluspunkt 0 Minuspunkte

2 Antworten

638 Aufrufe

Klassen NP-schwer und NP-vollständig

Gefragt 4, Feb 2017 in Kapitel 7 von udesf udesf Lernwillige(r) (200 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

96 Aufrufe

ndet. und det. Polynomialzeit

Gefragt 3, Feb 2017 in BER-AB von uodsh uodsh Eins-Komma-Null-Anwärter(in) (2.3k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

122 Aufrufe

HU-3-3 a) 2)

Gefragt 14, Dez 2016 in HU-3-1 von ubetj ubetj Lernwillige(r) (510 Punkte)

0 Pluspunkte 1 Minuspunkt

0 Antworten

75 Aufrufe

HU-3-3

Gefragt 21, Jul 2016 in AU-3-1 von usdqz usdqz Lernwillige(r) (440 Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

124 Aufrufe

SAT Exponentieller Zeit

Gefragt 14, Feb 2016 in 2014-H-05 von uzcwi uzcwi Lernwillige(r) (560 Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

83 Aufrufe

Wenn man die B=NP erst betrachtet:

Gefragt 13, Feb 2016 in 2012-H-05 von uzcwi uzcwi Lernwillige(r) (560 Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

723 Aufrufe

Was ist eine Diagonalsprache?

Gefragt 12, Feb 2016 in BER-AA von uyejk uyejk Lernwillige(r) (760 Punkte)

5 Pluspunkte 0 Minuspunkte

1 Antwort

177 Aufrufe

Warum liegen A und B in NP vollständig?

Gefragt 11, Feb 2016 in 2012-H-05 von uxduy uxduy Lernwillige(r) (470 Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

100 Aufrufe

BER-AI: NP-Schwer reduzierbar auf SAT, NP-Vollständig in Pol lösbar

Gefragt 7, Feb 2016 in Band I, Kapitel 10 von uagll uagll Lernwillige(r) (1.1k Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

130 Aufrufe

P=NP, was folgt daraus für NP-schwere Probleme?

Gefragt 7, Feb 2016 in Band I, Kapitel 10 von uxduz uxduz Lernwillige(r) (430 Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

335 Aufrufe

polynomielle reduzierbarkeit

Gefragt 28, Dez 2015 in BER-AA von ugeil ugeil Lernwillige(r) (1.2k Punkte)

1 Pluspunkt 0 Minuspunkte

2 Antworten

168 Aufrufe

Würde gerne wissen, ob meine Erklärungen für die einzelnen Aussagen stimmen

Gefragt 16, Okt 2015 in 2010-B-02 von updkn updkn Info-Genie (6.6k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

101 Aufrufe

ich verstehe nicht, warum die 8. Aussage falsch ist

Gefragt 16, Okt 2015 in 2010-B-02 von updkn updkn Info-Genie (6.6k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

92 Aufrufe

c): könnte man das $\leq$ auch als $<$ interpretieren?

Gefragt 29, Sep 2015 in 2009-N-04 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

60 Aufrufe

(3): Wieso ist keine Angabe zu einem Problem dieser Komplexitätsklasse möglich?

Gefragt 29, Sep 2015 in 2008-H-04 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

228 Aufrufe

alternative Argumentation, sodass clique_mod-c NP Schwierig?

Gefragt 29, Sep 2015 in 2011-N-05 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

2 Antworten

94 Aufrufe

b): Was bedeutet das "feste" k genau?

Gefragt 29, Sep 2015 in 2011-N-05 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

104 Aufrufe

c): Warum besteht die Kantenmenge aus max. n^2 Kanten?

Gefragt 25, Sep 2015 in 2013-H-05 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

111 Aufrufe

b): Erklärung der grundsätzlichen Vorgehensweise?

Gefragt 25, Sep 2015 in 2012-N-05 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

106 Aufrufe

b): könnten in "L1/L2)" auch NP-vollständige Probleme genannt werden?

Gefragt 25, Sep 2015 in 2011-H-05 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

72 Aufrufe

Wäre die Diagonalsprache auch ein korrektes Beispiel für die Antwort im b Teil der Aufgabe?

Gefragt 25, Sep 2015 in 2011-H-05 von uafjv uafjv Tutor(in) (168k Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

196 Aufrufe

Welche Komplexität hat das Halteproblem?

Gefragt 25, Sep 2015 in 2011-H-05 von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

94 Aufrufe

Wieso ist L nicht entscheidbar?

Gefragt 25, Sep 2015 in 2011-H-05 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

174 Aufrufe

was ist LNA für eine Sprachklasse?

Gefragt 25, Sep 2015 in 2011-H-05 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

54 Aufrufe

b): (3) - R min. in NP?

Gefragt 25, Sep 2015 in 2010-N-04 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

59 Aufrufe

b): (3) - R auch aus P?

Gefragt 25, Sep 2015 in 2010-N-04 von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 0 Minuspunkte

2 Antworten

1.2k Aufrufe

a): (2) Halteproblem - NP-schwer aber nicht mehr in NP?

Gefragt 25, Sep 2015 in 2010-N-04 von uafjv uafjv Tutor(in) (168k Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

76 Aufrufe

F in NP vollständig?