Die vorliegende Studienarbeit beschäftigt sich mit dem Artikel "Separating NC along the axis" von Bellantoni und Oitavem (ENTCS 2003). Darin wird ein Termsystem N* über Binärbäumen mit Blattspeicherung, angereichert um Konstanten für Baumrekursion, vorgestellt und im Stile Bellantoni/Niggl ein Maß auf N* erklärt. Das System N besteht dann aus genau den geschlossenen N*-Termen mit \rho-Maß kleiner order gleich 1.
Nach sorgfältiger Ausarbeitung der in der Arbeit dargestellten Ideen und Konstruktionen für den Beweis der Vollständigkeit des Systems N, daß nämlich jede NC-Funktion in System N definiert (berechnet) werden kann, kommt diese Studienarbeit zu dem Schluß, daß Vollständigkeit als zentrale Inklusion in der Charakterisierung von NC durch N so wie vorgestellt nicht gehalten werden kann.
%0 Generic
%1 macek2006quivalenzbetrachtungen
%A Macek, Karl Heinz Niggl Björn-Elmar
%D 2006
%K 2010 Complexity Equivalence Measures Recursion myown
%T Äquivalenzbetrachtungen zu den Klassen N und NC
%X Die vorliegende Studienarbeit beschäftigt sich mit dem Artikel "Separating NC along the axis" von Bellantoni und Oitavem (ENTCS 2003). Darin wird ein Termsystem N* über Binärbäumen mit Blattspeicherung, angereichert um Konstanten für Baumrekursion, vorgestellt und im Stile Bellantoni/Niggl ein Maß auf N* erklärt. Das System N besteht dann aus genau den geschlossenen N*-Termen mit \rho-Maß kleiner order gleich 1.
Nach sorgfältiger Ausarbeitung der in der Arbeit dargestellten Ideen und Konstruktionen für den Beweis der Vollständigkeit des Systems N, daß nämlich jede NC-Funktion in System N definiert (berechnet) werden kann, kommt diese Studienarbeit zu dem Schluß, daß Vollständigkeit als zentrale Inklusion in der Charakterisierung von NC durch N so wie vorgestellt nicht gehalten werden kann.
@misc{macek2006quivalenzbetrachtungen,
abstract = {Die vorliegende Studienarbeit beschäftigt sich mit dem Artikel "Separating NC along the \delta axis" von Bellantoni und Oitavem (ENTCS 2003). Darin wird ein Termsystem N* über Binärbäumen mit Blattspeicherung, angereichert um Konstanten für Baumrekursion, vorgestellt und im Stile Bellantoni/Niggl ein Maß \rho auf N* erklärt. Das System N besteht dann aus genau den geschlossenen N*-Termen mit \rho-Maß kleiner order gleich 1.
Nach sorgfältiger Ausarbeitung der in der Arbeit dargestellten Ideen und Konstruktionen für den Beweis der Vollständigkeit des Systems N, daß nämlich jede NC-Funktion in System N definiert (berechnet) werden kann, kommt diese Studienarbeit zu dem Schluß, daß Vollständigkeit als zentrale Inklusion in der Charakterisierung von NC durch N so wie vorgestellt nicht gehalten werden kann.},
added-at = {2010-06-09T16:27:49.000+0200},
author = {Macek, Karl Heinz Niggl Björn-Elmar},
biburl = {https://www.bibsonomy.org/bibtex/268f72b536640097d2187db01c8a5c23a/macek},
interhash = {f0b9e3047ecd242aab43654bd95108e1},
intrahash = {68f72b536640097d2187db01c8a5c23a},
keywords = {2010 Complexity Equivalence Measures Recursion myown},
timestamp = {2011-11-03T14:00:08.000+0100},
title = {Äquivalenzbetrachtungen zu den Klassen N und NC},
year = 2006
}