Diskussion:Trivialität

Zum Archiv

Wie wird ein Archiv angelegt?

Auf dieser Seite werden Abschnitte ab Überschriftebene 2 automatisch archiviert, die seit 7 Tagen mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind.

Trivialität in der Komplexitätstheorie

Ich habe folgenden Satz entfernt:

Es (d.h. die Probleme, immer zu akzeptieren bzw. immer zu verwerfen) sind außerdem die einzigen in konstanter Zeit (O(1) in Landau-Notation) lösbaren Probleme.

Dieser Satz ist falsch. So ist z.B. auch das Problem "Akzeptiere, falls das erste Zeichen der Eingabe eine 0 ist" in konstanter Zeit lösbar, da man ja eben nur dieses eine Zeichen testen muss. Kann das irgendjemand "sichten"? Keine Ahnung, wie das funktioniert. --128.178.42.58 15:57, 25. Feb. 2009 (CET)

Man sollte den Abschnitt vielleicht nicht so sehr auf die Komplexitätstheorie einschränken, sondern besser "... in der Theoretischen Informatik" schreiben, da der gleiche Begriff von trivialen Problemen auch beispielsweise im Satz von Rice Verwendung findet, der mit Komplexitätstheorie nichts zu tun hat. -- Dodoline 13:41, 18. Mär. 2010 (CET)

Injektiv?

Die reduzierende Funktion muss in der mir bekannten Definition (z.B. bei Erk/Priese) nicht injektiv sein. Woher kommt die Information, sie müsse es? -- UKoch 16:58, 12. Dez. 2011 (CET)

Hm, ich habe offenbar das "Turing" in "Turing-Reduktion" nicht genügend beachtet. -- UKoch 16:32, 21. Dez. 2011 (CET)

Wie in dem entsprechenden Artikel zu lesen ist, muss die Reduktionsfunktion nicht injektiv sein (sie kann es aber sein). -- LordObama 22:15, 21. Jul. 2018 (CET)

Etymologie

Der Duden liegt hier mMn falsch, das Wort kommt von Trivium: Trivium --80.187.108.98 19:39, 25. Aug. 2022 (CEST)