Diskussion:Reduktion (theoretische Informatik)

Vollständigkeit

Am 10.03.2010, also vor 10 Tagen, habe ich den Satz "Ein Problem ist vollständig für eine Komplexitätsklasse, wenn jedes andere Problem der Klasse darauf reduziert werden kann." in "Ein Problem ist vollständig für eine Komplexitätsklasse, wenn es selbst dieser Klasse angehört und jedes andere Problem der Klasse darauf reduziert werden kann." geändert, da es sich zuvor nur um die Schwere handelte, nicht die Vollständigkeit. Ich möchte einen befähigten Mithelfer darum bitten, die Änderung endlich zuzulassen. (nicht signierter Beitrag von 84.59.9.168 (Diskussion | Beiträge) 08:45, 20. Mär. 2010 (CET))

Definition Orakel TM

Sollte man die Orakel TM nicht noch definieren, oder wenigstens darauf verlinken?

Wortbedeutung Reduktion

Ich bin mir nicht ganz sicher: Reduktion bedeutet hier ja nicht Vereinfachung (das ist es ja eigentlich nicht) sondern Zurückführung (reducere, siehe z.B. im wictionary unter "reduzieren"). Wäre hilfreich um Missverständnisse zu vermeiden.

Neubearbeitung

Ich habe mich mal an einer Neubearbeitung des Artikels versucht, da ich ihn als Ausgangspunkt für einige neue Projekte nutzen will, wie beispielsweise Schwere (Theoretische Informatik) oder Vollständigkeit (Theoretische Informatik) - in dem dann Vollständigkeit (Komplexitätstheorie) aufgehen soll - sowie die Zusammenlegung der Ein-Zeilen-Artikel NP-leicht und NP-Äquivalenz.

Es wäre auch eine Idee den einzelnen Arten von Reduktionen in eigenen Artikeln mehr Platz einzuräumen, aber selbst in der englischen Wikipedia sind dies meist nur Stubs... mal sehen. Da meine Zeit aktuell sehr stark limitiert ist, wäre ich für aktive Mithilfe und natürlich Lob, Kritik oder Anregungen sehr dankbar.

-- 89.16.150.130 02:56, 23. Mai 2013 (CEST)

Sprachlinks

M.M.n. passt folgender Hinweis besser in die Artikel Disk. als an die entsprechende Stelle bei Wikidata:

"Reduktion (Theoretische Informatik)" scheint (auf Grund seiner Versionsgeschichte?) in den anderen Sprachen durchweg mit den jeweiligen Artikel zur Reduktion in der Komplexitätstheorie verlinkt zu sein. Dies ist auch dann der Fall wenn in der betreffenden Sprache ein Artikel mit dem weiteren Blickwinkel der theoretischen Informatik/Rekursionstheorie vorhanden ist. (Überprüft für Englisch und Portugiesisch.) Umgekehrt blokieren diese Artikel dann mit ihren jeweiligen Sprachlinks jegliche Edits für die Links hier, à la "A zeigt auf B, dann kann B (auch nicht für die Zeit eines Edits) auf C zeigen." Meine Bitte daher: Könnte jemand, der sich besser als ich mit Wikidata auskennt, die Links so anpassen, dass sie - falls vorhanden - auf den jeweils richtigen Artikel (Red. i.d. theo.Inf./Rekursionsth.) zeigen?

Vielen Dank und liebe Grüße

-- 2A02:8109:A7BF:E964:C99F:43CA:5CF7:19F5 10:07, 23. Sep. 2015 (CEST)