Letzte Fragen & Antworten in Berechenbarkeits- und Komplexitätstheorie

0 Pluspunkte 0 Minuspunkte

1 Antwort

38 Aufrufe

Ist es bei abzählbaren Mengen auch eine berechenbare Funktion oder nur irgendeine Funktion?

Beantwortet 22, Jan 2022 in BER-AK von uvlwv uvlwv Info-Genie (9.4k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

40 Aufrufe

Sprache welche albzählbar aber nicht aufzählbar ist?

Beantwortet 11, Jan 2022 in BER-AK von uvlwv uvlwv Info-Genie (9.4k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

37 Aufrufe

erklarung

Beantwortet 2, Jan 2022 in BER-AB von ubxvl ubxvl Lernwillige(r) (340 Punkte)

0 Pluspunkte 0 Minuspunkte

0 Antworten

36 Aufrufe

nicht entscheidbar

Gefragt 4, Jul 2021 in BER-AB von uqyxt uqyxt Lernwillige(r) (640 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

201 Aufrufe

Knoten im Kopf bzgl. Entscheidbarkeit

Beantwortet 11, Feb 2020 in BER-AA von udjza udjza Lernwillige(r) (800 Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

131 Aufrufe

Berechenbarkeit Folie GdI2 V13-68 (Seite 68)

Beantwortet 10, Feb 2020 in BER-AA von Tatiana Landesberger von Antburg Lernwillige(r) (670 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

154 Aufrufe

Frage zur Notation Definition Halteproblem

Beantwortet 10, Feb 2020 in BER-AA von Tatiana Landesberger von Antburg Lernwillige(r) (670 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

327 Aufrufe

Beispiel abzählbare, nicht aufzählbare Menge

Beantwortet 10, Feb 2020 in BER-AG von unort unort Eins-Komma-Null-Anwärter(in) (3.9k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

204 Aufrufe

Halteproblem - Beweis

Beantwortet 9, Feb 2020 in BER-AA von unort unort Eins-Komma-Null-Anwärter(in) (3.9k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

102 Aufrufe

Definition Halteproblem

Beantwortet 4, Feb 2020 in BER-AA von unort unort Eins-Komma-Null-Anwärter(in) (3.9k Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

250 Aufrufe

Klausurrelevanz Komplexitätsklassen

Beantwortet 3, Feb 2020 in BER-AB von unort unort Eins-Komma-Null-Anwärter(in) (3.9k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

141 Aufrufe

Sind in semientscheidbaren Problemen auch unentscheidbare Probleme enthalten?

Beantwortet 10, Feb 2019 in BER-AA von upfgy upfgy Eins-Komma-Null-Anwärter(in) (1.8k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

143 Aufrufe

Warum sind abzählbare, aber nicht aufzählbare Mengen nicht entscheidbar?

Beantwortet 10, Feb 2019 in BER-AA von uvlwv uvlwv Info-Genie (9.4k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

121 Aufrufe

Aufzählbare Mengen können nicht unendlich sein?

Beantwortet 10, Feb 2019 in BER-AA von uvlwv uvlwv Info-Genie (9.4k Punkte)

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

Beantwortet 7, Feb 2019 in BER-AH von uneoo uneoo Eins-Komma-Null-Anwärter(in) (2.4k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

176 Aufrufe

dies ist ein test

Beantwortet 2, Okt 2018 in BER-AA von Niclas Kannengießer Übungsleiter(in) (1.0m Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

89 Aufrufe

C nicht in Polynomialzeit lösbar ?

Beantwortet 7, Feb 2018 in BER-AH von Anonym

0 Pluspunkte 0 Minuspunkte

1 Antwort

323 Aufrufe

Reduzierbarkeit

Beantwortet 8, Jan 2018 in BER-AI von ureif ureif Tutor(in) (101k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

103 Aufrufe

Reduzierbarkeit

Beantwortet 7, Jan 2018 in BER-AI von ugeib ugeib Tutor(in) (101k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

365 Aufrufe

Polynomialzeitreduktion und Komplexitätsklasse

Beantwortet 15, Okt 2017 in BER-AA von Dozent (10.1m Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

95 Aufrufe

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

Beantwortet 17, Jul 2017 in BER-AL von Dozent (10.1m Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

96 Aufrufe

ndet. und det. Polynomialzeit

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

0 Pluspunkte 0 Minuspunkte

1 Antwort

183 Aufrufe

c) Frage 3 Verständnis

Beantwortet 3, Jan 2017 in BER-AG von Dozent (10.1m Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

723 Aufrufe

Was ist eine Diagonalsprache?

Beantwortet 13, Feb 2016 in BER-AA von uedqi uedqi Tutor(in) (109k Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

1.0k 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) (103k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

133 Aufrufe

Entscheidbarkeit

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

2 Pluspunkte 0 Minuspunkte

1 Antwort

335 Aufrufe

polynomielle reduzierbarkeit

Beantwortet 29, Dez 2015 in BER-AA von uldbw uldbw Tutor(in) (101k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

723 Aufrufe

Abzählbare Menge Teilmenge von Aufzählbar?

Beantwortet 26, Jan 2015 in BER-AG von Dozent (10.1m Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

93 Aufrufe

Warum bei c) $Y \in NP$?

Beantwortet 16, Jan 2015 in BER-AA von uedqi uedqi Tutor(in) (109k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

122 Aufrufe

trival also echt kleiner als P?

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

333 Aufrufe

Schreiben von Pseudocode klausurrelevant?

Beantwortet 26, Nov 2014 in BER-AG von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

107 Aufrufe

was bedeutet aufzählbar ?

Beantwortet 26, Nov 2014 in BER-AG von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

127 Aufrufe

Verständnisporblem zu anhalten/nicht-anhalten von TM

Beantwortet 26, Nov 2014 in BER-AG von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

159 Aufrufe

Zusammenhang der ganzen Komplexitätsklassen mit SAT/CLIQUE

Beantwortet 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (168k Punkte)

1 Pluspunkt 1 Minuspunkt

1 Antwort

131 Aufrufe

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

Beantwortet 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

112 Aufrufe

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

Beantwortet 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

304 Aufrufe

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

Beantwortet 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

122 Aufrufe

Teil e) Was bedeutet P = NP

Beantwortet 26, Nov 2014 in BER-AA von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

2 Antworten

141 Aufrufe

warum liegt A nicht in NP ?

Beantwortet 26, Nov 2014 in BER-AA von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

144 Aufrufe

Teil a) Definition von M'

Beantwortet 25, Nov 2014 in BER-AD von uafjv uafjv Tutor(in) (168k Punkte)

0 Pluspunkte 1 Minuspunkt

1 Antwort

92 Aufrufe

Warrum 5. und 7. Aussage falsch?

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

0 Pluspunkte 1 Minuspunkt

2 Antworten

120 Aufrufe

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

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

115 Aufrufe

Jedes NP-schwere Problem reduzierbar?