Trivialität

Triviale Probleme werden im Zusammenhang mit der Turing-Reduktion in der Komplexitätsklasse P erwähnt. In dieser sind es die beiden Probleme, auf die sich die anderen der Klasse P nicht Turing-reduzieren lassen. Es handelt sich um das Problem „Immer akzeptieren“ und dessen Komplement „Immer verwerfen“. Bei der Turing-Reduktion werden alle Instanzen des Ursprungsproblems auf Instanzen des Zielproblems abgebildet. Dabei werden Ja-Instanzen auf Ja-Instanzen und Nein-Instanzen auf Nein-Instanzen abgebildet. Die trivialen Probleme weisen jedoch nur einen der beiden Instanzentypen auf, sodass die Instanzen des anderen nicht abgebildet werden können.

Eine nichttriviale Eigenschaft einer nichtleeren Menge ist eine Eigenschaft, die einige, aber nicht alle Elemente der Menge besitzen. Nach dem Satz von Rice ist jede nichttriviale semantische (im Gegensatz zu „syntaktische“, d. h. an der Zeichenfolge des Programmtexts unmittelbar ablesbare) Eigenschaft ${\displaystyle E}$ eines Programms unentscheidbar. Das Problem, herauszufinden, ob ein vorgegebenes Programm die Eigenschaft ${\displaystyle E}$ hat, ist also algorithmisch nicht lösbar.

Methoden oder andere Dienste mit der Aufgabe, etwas zu suchen beziehungsweise zu finden, können als trivial oder nicht-trivial bezeichnet werden.

• Trivial sind solche, die eine Variable oder einen anderen einfachen Wert, auf den sie zugreifen können, zurückgeben.
• Nicht-trivial sind solche, die den gesuchten Wert zuerst finden müssen. Dabei wird meistens eine bestimmte Eigenschaft referenziert. Diese wird dann in einer Sammlung oder einem listenähnlichen Konstrukt nach diversen Kriterien gesucht und danach zurückgegeben.

Mathematische Objekte, Aussagen oder Eigenschaften heißen trivial, wenn sie besonders einfach angegeben werden können, d. h. sich ohne jedes Zutun aus einer Definition oder einem Satz ergeben.[3]

• Die trivialen Teiler einer natürlichen Zahl ${\displaystyle n}$ sind ${\displaystyle 1}$ und ${\displaystyle n}$ selbst. Man kann sie angeben, ohne Näheres (wie beispielsweise die Primfaktorzerlegung) über ${\displaystyle n}$ zu wissen. Alle anderen Teiler heißen nichttriviale oder echte Teiler.

• Die triviale Lösung eines homogenen linearen Gleichungssystems ${\displaystyle Ax=0}$ ist die Nulllösung ${\displaystyle x=0}$. Man kann sie angeben, ohne Näheres über ${\displaystyle A}$ zu wissen. Alle anderen Lösungen heißen nichttriviale Lösungen.

• Triviale Teilmengen einer Menge sind die leere Menge und die Menge selbst. Alle anderen Teilmengen heißen echte Teilmengen.

• Eine triviale Gruppe ${\displaystyle (\{e\},*)}$ ist eine Gruppe, die nur aus einem Element ${\displaystyle e}$ und der einzig möglichen trivialen Operation ${\displaystyle e*e=e}$ besteht.
• Ein trivialer Ring ${\displaystyle (\{0\},+,\,\cdot \,)}$ ist ein Ring, der nur aus dem Nullelement ${\displaystyle 0}$ und den zwei Operationen ${\displaystyle 0+0=0}$ und ${\displaystyle 0\cdot 0=0}$ besteht.