R (Komplexität)
Im Computerkomplexitätstheorie, R ist die Klasse von Entscheidungsprobleme lösbar durch a Turing Maschine, das ist das Set von allen rekursive Sprachen (auch als lehnte Sprachen bezeichnet).
Äquivalente Formulierungen
R entspricht dem Satz aller Gesamtmenge berechnungsbare Funktionen in dem Sinne, dass:
- Ein Entscheidungsproblem ist in R, wenn und nur wenn es ist Indikatorfunktion ist rechenbar,
- Eine Gesamtfunktion ist nur dann berechnet, wenn es ihre Graph ist in R.
Beziehung zu anderen Klassen
Da können wir jedes Problem entscheiden, für das es vorhanden ist Erkenntnis und auch ein Miterkenner, indem sie einfach verschoben werden, bis man ein Ergebnis erzielt, die Klasse ist gleich BETREFFEND ∩ Ader.
Verweise
- Blum, Lenore, Mike Shub und Steve Smale, (1989), "über eine Theorie der Berechnung und Komplexität über die realen Zahlen: NP-Vervollständigung, rekursive Funktionen und universelle Maschinen", Bulletin der American Mathematical Society, Neue Serien, 21 (1): 1-46.
Externe Links