Letzte Fragen in Berechenbarkeits- und Komplexitätstheorie

0 Punkte

1 Antwort

83 Aufrufe

dies ist ein test

Gefragt 18 Jun in BER-AA von Lukas König Dozent (10,064,890 Punkte)

0 Punkte

1 Antwort

38 Aufrufe

C nicht in Polynomialzeit lösbar ?

Gefragt 7 Feb in BER-AH von Anonym

0 Punkte

1 Antwort

117 Aufrufe

Reduzierbarkeit

Gefragt 8 Jan in BER-AI von Anonym

0 Punkte

1 Antwort

24 Aufrufe

Reduzierbarkeit

Gefragt 6 Jan in BER-AI von Anonym

+1 Punkt

1 Antwort

53 Aufrufe

Polynomialzeitreduktion und Komplexitätsklasse

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

+1 Punkt

1 Antwort

25 Aufrufe

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

Gefragt 17, Jul 2017 in BER-AL von Anonym

0 Punkte

1 Antwort

48 Aufrufe

ndet. und det. Polynomialzeit

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

0 Punkte

1 Antwort

123 Aufrufe

c) Frage 3 Verständnis

Gefragt 3, Jan 2017 in BER-AG von uqebf uqebf Lernwillige(r) (170 Punkte)

+2 Punkte

1 Antwort

168 Aufrufe

Was ist eine Diagonalsprache?

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

+1 Punkt

1 Antwort

462 Aufrufe

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

Gefragt 11, Feb 2016 in BER-AI von utdtz utdtz Eins-Komma-Null-Anwärter(in) (3,060 Punkte)

+1 Punkt

1 Antwort

61 Aufrufe

Entscheidbarkeit

Gefragt 8, Feb 2016 in BER-AH von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4,190 Punkte)

+2 Punkte

1 Antwort

80 Aufrufe

polynomielle reduzierbarkeit

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

+1 Punkt

1 Antwort

50 Aufrufe

Abzählbare Menge Teilmenge von Aufzählbar?

Gefragt 26, Jan 2015 in BER-AG von uxdou uxdou Lernwillige(r) (190 Punkte)

–1 Punkt

1 Antwort

54 Aufrufe

Warum bei c) $Y \in NP$?

Gefragt 16, Jan 2015 in BER-AA von uceae uceae Lernwillige(r) (110 Punkte)

+1 Punkt

1 Antwort

64 Aufrufe

trival also echt kleiner als P?

Gefragt 10, Jan 2015 in BER-AA von uxdko uxdko Lernwillige(r) (420 Punkte)

–1 Punkt

1 Antwort

276 Aufrufe

Schreiben von Pseudocode klausurrelevant?

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

–1 Punkt

1 Antwort

44 Aufrufe

was bedeutet aufzählbar ?

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

–1 Punkt

1 Antwort

49 Aufrufe

Verständnisporblem zu anhalten/nicht-anhalten von TM

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

–1 Punkt

1 Antwort

69 Aufrufe

Zusammenhang der ganzen Komplexitätsklassen mit SAT/CLIQUE

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

0 Punkte

1 Antwort

51 Aufrufe

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

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

–1 Punkt

1 Antwort

41 Aufrufe

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

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

–1 Punkt

1 Antwort

122 Aufrufe

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

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

–1 Punkt

1 Antwort

48 Aufrufe

Teil e) Was bedeutet P = NP

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

–1 Punkt

2 Antworten

56 Aufrufe

warum liegt A nicht in NP ?

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

–1 Punkt

1 Antwort

63 Aufrufe

Teil a) Definition von M'

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

–1 Punkt

1 Antwort

29 Aufrufe

Warrum 5. und 7. Aussage falsch?

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

–1 Punkt

2 Antworten

61 Aufrufe

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

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

–1 Punkt

1 Antwort

58 Aufrufe

Jedes NP-schwere Problem reduzierbar?