%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 = {2015-10-13T12:13:39.000+0200}, author = {Macek, Karl Heinz Niggl Björn-Elmar}, biburl = {https://www.bibsonomy.org/bibtex/268f72b536640097d2187db01c8a5c23a/kde-alumni}, interhash = {f0b9e3047ecd242aab43654bd95108e1}, intrahash = {68f72b536640097d2187db01c8a5c23a}, keywords = {2010 Complexity Equivalence Measures Recursion myown}, timestamp = {2016-11-29T17:45:16.000+0100}, title = {Äquivalenzbetrachtungen zu den Klassen N und NC}, year = 2006 }