Nichtdeterministische Turing-Maschinen

Nichtdeterministische Turing-Maschinen können während ihrer Berechnung raten. Da es häufiger einfacher ist, eine gefundene Lösung zu überprüfen, als die Lösung zu bestimmen, können diese Maschinen bestimmte Probleme einfach lösen. Wir zeigen, dass sie aber nicht "mehr können" als normale deterministische Turing-Maschinen, die nicht raten dürfen. Sie sind nur u.U. schneller.

[@JerryOmann]

Sehr gut ! Vielen Dank für die tolle Erklärung (:

[@princeelliot2836]

Vielen Dank für deine sehr interessanten und hilfreichen Videos.