Diskussion:Trivialität
aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 25. August 2022 um 17:39 Uhr durch imported>Anonym~dewiki(31560) (Neuer Abschnitt →Etymologie).
| 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)
