Letzte Fragen & Antworten in Berechenbarkeits- und Komplexitätstheorie

0 Punkte

1 Antwort

100 Aufrufe

dies ist ein test

Beantwortet 2, Okt 2018 in BER-AA von Niclas Kannengießer Übungsleiter(in) (1,000,160 Punkte)

0 Punkte

1 Antwort

40 Aufrufe

C nicht in Polynomialzeit lösbar ?

Beantwortet 7, Feb 2018 in BER-AH von Anonym

0 Punkte

1 Antwort

130 Aufrufe

Reduzierbarkeit

Beantwortet 8, Jan 2018 in BER-AI von ureif ureif Tutor(in) (100,900 Punkte)

0 Punkte

1 Antwort

26 Aufrufe

Reduzierbarkeit

Beantwortet 7, Jan 2018 in BER-AI von ugeib ugeib Tutor(in) (100,640 Punkte)

+1 Punkt

1 Antwort

57 Aufrufe

Polynomialzeitreduktion und Komplexitätsklasse

Beantwortet 15, Okt 2017 in BER-AA von Lukas König Dozent (10,064,890 Punkte)

+1 Punkt

1 Antwort

27 Aufrufe

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

Beantwortet 17, Jul 2017 in BER-AL von Lukas König Dozent (10,064,890 Punkte)

0 Punkte

1 Antwort

51 Aufrufe

ndet. und det. Polynomialzeit

Beantwortet 3, Feb 2017 in BER-AB von ufdrm ufdrm Tutor(in) (102,020 Punkte)

0 Punkte

1 Antwort

124 Aufrufe

c) Frage 3 Verständnis

Beantwortet 3, Jan 2017 in BER-AG von Lukas König Dozent (10,064,890 Punkte)

+2 Punkte

1 Antwort

174 Aufrufe

Was ist eine Diagonalsprache?

Beantwortet 13, Feb 2016 in BER-AA von uedqi uedqi Tutor(in) (108,510 Punkte)

+1 Punkt

1 Antwort

490 Aufrufe

Kann ich ein NP-schweres Problem auf ein NP-vollständiges Problem reduzieren?

Beantwortet 11, Feb 2016 in BER-AI von ukean ukean Tutor(in) (103,040 Punkte)

+1 Punkt

1 Antwort

63 Aufrufe

Entscheidbarkeit

Beantwortet 8, Feb 2016 in BER-AH von ukean ukean Tutor(in) (103,040 Punkte)

+2 Punkte

1 Antwort

81 Aufrufe

polynomielle reduzierbarkeit

Beantwortet 29, Dez 2015 in BER-AA von uldbw uldbw Tutor(in) (100,600 Punkte)

+1 Punkt

1 Antwort

52 Aufrufe

Abzählbare Menge Teilmenge von Aufzählbar?

Beantwortet 26, Jan 2015 in BER-AG von Lukas König Dozent (10,064,890 Punkte)

–1 Punkt

1 Antwort

55 Aufrufe

Warum bei c) $Y \in NP$?

Beantwortet 16, Jan 2015 in BER-AA von uedqi uedqi Tutor(in) (108,510 Punkte)

+1 Punkt

1 Antwort

65 Aufrufe

trival also echt kleiner als P?

Beantwortet 12, Jan 2015 in BER-AA von ufdrm ufdrm Tutor(in) (102,020 Punkte)

–1 Punkt

1 Antwort

278 Aufrufe

Schreiben von Pseudocode klausurrelevant?

Beantwortet 26, Nov 2014 in BER-AG von uafjv uafjv Tutor(in) (166,490 Punkte)

–1 Punkt

1 Antwort

45 Aufrufe

was bedeutet aufzählbar ?

Beantwortet 26, Nov 2014 in BER-AG von uafjv uafjv Tutor(in) (166,490 Punkte)

–1 Punkt

1 Antwort

53 Aufrufe

Verständnisporblem zu anhalten/nicht-anhalten von TM

Beantwortet 26, Nov 2014 in BER-AG von uafjv uafjv Tutor(in) (166,490 Punkte)

–1 Punkt

1 Antwort

71 Aufrufe

Zusammenhang der ganzen Komplexitätsklassen mit SAT/CLIQUE

Beantwortet 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (166,490 Punkte)

0 Punkte

1 Antwort

53 Aufrufe

$A \notin EXPTIME \backslash PSPACE$: Verständnisproblem

Beantwortet 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (166,490 Punkte)

–1 Punkt

1 Antwort

43 Aufrufe

vorletzten Aussage: richtig, weil entscheidbar eine Teilmenge von semientscheidbar?

Beantwortet 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (166,490 Punkte)

–1 Punkt

1 Antwort

131 Aufrufe

2. Aussage: Warum ist ( A <=pol C) richtig ?

Beantwortet 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (166,490 Punkte)

–1 Punkt

1 Antwort

49 Aufrufe

Teil e) Was bedeutet P = NP

Beantwortet 26, Nov 2014 in BER-AA von uafjv uafjv Tutor(in) (166,490 Punkte)

–1 Punkt

2 Antworten

57 Aufrufe

warum liegt A nicht in NP ?

Beantwortet 26, Nov 2014 in BER-AA von uafjv uafjv Tutor(in) (166,490 Punkte)

–1 Punkt

1 Antwort

65 Aufrufe

Teil a) Definition von M'

Beantwortet 25, Nov 2014 in BER-AD von uafjv uafjv Tutor(in) (166,490 Punkte)

–1 Punkt

1 Antwort

31 Aufrufe

Warrum 5. und 7. Aussage falsch?

Beantwortet 23, Nov 2014 in BER-AL von uyctv uyctv Info-Genie (18,950 Punkte)

–1 Punkt

2 Antworten

64 Aufrufe

Was bedeutet $Q \leq_{pol} P \wedge Q$?

Beantwortet 23, Nov 2014 in BER-AL von uyctv uyctv Info-Genie (18,950 Punkte)

–1 Punkt

1 Antwort

60 Aufrufe

Jedes NP-schwere Problem reduzierbar?