Letzte Fragen in Berechenbarkeits- und Komplexitätstheorie

0 Pluspunkte 0 Minuspunkte

1 Antwort

26 Aufrufe

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

Gefragt 11 Jan in BER-AK von upmtz upmtz Lernwillige(r) (140 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

27 Aufrufe

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

Gefragt 10 Jan in BER-AK von upmtz upmtz Lernwillige(r) (140 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

28 Aufrufe

erklarung

Gefragt 20, Dez 2021 in BER-AB von uqyxt uqyxt Lernwillige(r) (640 Punkte)

0 Pluspunkte 0 Minuspunkte

0 Antworten

30 Aufrufe

nicht entscheidbar

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

0 Pluspunkte 0 Minuspunkte

1 Antwort

191 Aufrufe

Knoten im Kopf bzgl. Entscheidbarkeit

Gefragt 10, Feb 2020 in BER-AA von uhevv uhevv Lernwillige(r) (1.3k Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

279 Aufrufe

Beispiel abzählbare, nicht aufzählbare Menge

Gefragt 9, Feb 2020 in BER-AG von uzsst uzsst Lernwillige(r) (180 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

192 Aufrufe

Halteproblem - Beweis

Gefragt 9, Feb 2020 in BER-AA von uovhe uovhe Lernwillige(r) (290 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

91 Aufrufe

Definition Halteproblem

Gefragt 4, Feb 2020 in BER-AA von uhevv uhevv Lernwillige(r) (1.3k Punkte)

2 Pluspunkte 0 Minuspunkte

1 Antwort

226 Aufrufe

Klausurrelevanz Komplexitätsklassen

Gefragt 3, Feb 2020 in BER-AB von ueodr ueodr Lernwillige(r) (660 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

148 Aufrufe

Frage zur Notation Definition Halteproblem

Gefragt 29, Jan 2020 in BER-AA von uhevv uhevv Lernwillige(r) (1.3k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

121 Aufrufe

Berechenbarkeit Folie GdI2 V13-68 (Seite 68)

Gefragt 24, Jan 2020 in BER-AA von uhevv uhevv Lernwillige(r) (1.3k Punkte)

0 Pluspunkte 0 Minuspunkte

0 Antworten

390 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

113 Aufrufe

Aufzählbare Mengen können nicht unendlich sein?

Gefragt 9, Feb 2019 in BER-AA von uuuwm uuuwm Lernwillige(r) (160 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

131 Aufrufe

Sind in semientscheidbaren Problemen auch unentscheidbare Probleme enthalten?

Gefragt 9, Feb 2019 in BER-AA von uuuwm uuuwm Lernwillige(r) (160 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

134 Aufrufe

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

Gefragt 9, Feb 2019 in BER-AA von uuuwm uuuwm Lernwillige(r) (160 Punkte)

0 Pluspunkte 0 Minuspunkte

1 Antwort

175 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

171 Aufrufe

dies ist ein test

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

1 Pluspunkt 0 Minuspunkte

1 Antwort

81 Aufrufe

C nicht in Polynomialzeit lösbar ?

Gefragt 7, Feb 2018 in BER-AH von Anonym

0 Pluspunkte 0 Minuspunkte

1 Antwort

302 Aufrufe

Reduzierbarkeit

Gefragt 8, Jan 2018 in BER-AI von Anonym

0 Pluspunkte 0 Minuspunkte

1 Antwort

91 Aufrufe

Reduzierbarkeit

Gefragt 6, Jan 2018 in BER-AI von Anonym

1 Pluspunkt 0 Minuspunkte

1 Antwort

342 Aufrufe

Polynomialzeitreduktion und Komplexitätsklasse

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

1 Pluspunkt 0 Minuspunkte

1 Antwort

89 Aufrufe

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

Gefragt 17, Jul 2017 in BER-AL von Anonym

0 Pluspunkte 0 Minuspunkte

1 Antwort

88 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

175 Aufrufe

c) Frage 3 Verständnis

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

2 Pluspunkte 0 Minuspunkte

1 Antwort

589 Aufrufe

Was ist eine Diagonalsprache?

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

2 Pluspunkte 0 Minuspunkte

1 Antwort

936 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.1k Punkte)

1 Pluspunkt 0 Minuspunkte

1 Antwort

120 Aufrufe

Entscheidbarkeit

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

2 Pluspunkte 0 Minuspunkte

1 Antwort

322 Aufrufe

polynomielle reduzierbarkeit

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

1 Pluspunkt 0 Minuspunkte

1 Antwort

694 Aufrufe

Abzählbare Menge Teilmenge von Aufzählbar?

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

82 Aufrufe

Warum bei c) $Y \in NP$?

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

1 Pluspunkt 0 Minuspunkte

1 Antwort

110 Aufrufe

trival also echt kleiner als P?

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

318 Aufrufe

Schreiben von Pseudocode klausurrelevant?

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

94 Aufrufe

was bedeutet aufzählbar ?

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

109 Aufrufe

Verständnisporblem zu anhalten/nicht-anhalten von TM

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

129 Aufrufe

Zusammenhang der ganzen Komplexitätsklassen mit SAT/CLIQUE

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

1 Pluspunkt 1 Minuspunkt

1 Antwort

114 Aufrufe

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

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

96 Aufrufe

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

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

282 Aufrufe

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

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

109 Aufrufe

Teil e) Was bedeutet P = NP

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

0 Pluspunkte 1 Minuspunkt

2 Antworten

115 Aufrufe

warum liegt A nicht in NP ?

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

129 Aufrufe

Teil a) Definition von M'

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

80 Aufrufe

Warrum 5. und 7. Aussage falsch?

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

0 Pluspunkte 1 Minuspunkt

2 Antworten

114 Aufrufe

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

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

0 Pluspunkte 1 Minuspunkt

1 Antwort

100 Aufrufe

Jedes NP-schwere Problem reduzierbar?