Über die Erfüllung gewisser Erhaltungssätze durch Kompliziertheitsmasse

✍ Scribed by Gerhard Lischke

• Publisher: John Wiley and Sons
• Year: 1975
• Tongue: English
• Weight: 567 KB
• Volume: 21
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19750210121

✦ Synopsis

GEWISSER ERHALTUNGSSATZE DURCH KOMPLIZIERTHEITSMASSE von GEHHARD LISCHKE in Jena (DDR) I. Einlcitung I)urch die Arbeiten von M. 0. RABIN [6] und M. BLUM [l] hat die Kompliziertheitstheorit eine axiomatisehe Begrundung erfahren. Die auf den beiden BLnMschen Axiomen fiir Kompliziertheitsmale (siehe Abschnitt 2) beruhende Theorie ifit bereits verhaltnis-miI3ig weit entwickelt (vgl. M. BLUM [l] und J. HARTMANIS und J. E. HOPCROFT [4]), i e bcsitzt aber einen gewissen Nachteil, dcr darin besteht, d a l in ihr Kompliziertheitsm a k mit ziemlich pathologischen Kigenschaften vorkommen (vgl. J. HARTMANIS [3]).

Es crhebt sich also das Problem, durch zusatzliche Axiome eine groBere ,,Naturlichkeit" der Mane zu sichern [3]. I n der vorliegenden Arbeit werden dazu gewisse ,,Erhaltungs-&tzc" gefordert (Abschnitt 2). Man kann sich leicht davon iiberzeugen, da0 alle naturlichen KompliziertheitsmaBe geeignete Erhaltungssatze erfiillen, und es zeigt sich, d a l auch bci relativ weiter Fassung der Erhaltungssatze nicht jedes BLuMsche Ma13 einen eolchcn erfiillt. Die Forderung solcher Erhaltungssiitze stellt also eine echte Einschrankung a n die Menge der Kompliziertheitsmale dar. Es bleibt weiteren Untersuchungen vorbchalten, festzustellen, inwieweit die durch Erhaltungssatze definierten Komplieiert ht4tsmaDe Natiirlichkeitsforderungen, wie sie etwa in [3] formuliert sind, genugen. In dcr vorliegenden Arbeit werden weiterhin einige Beziehungen zwischen BLuMschen KompliziertheitsmaDen und den beiden Bestimmungsstucken fur Erhaltungssiitze untersucht.

Die Grundidee der vorliegenden Arbeit und den Ansatz fur die Erhaltungssatze aowit die Ausgangsidee fur den Beweis des Satzes 2 verdanke ich Herrn G. WECHSUNCI in Jena.

2. Definitionen

EH sei y o , yl, Q)~, . . . eine GoDELisierung aller ehstelligen partiell-rekumiven Funktionen. Eine zweistellige partiell-rekursive Funktion @ heil3t (Blumches) K m p l i z i e r f -kilSnuz/?, wenn sie die beiden folgenden Axiome erfiillt [l]:

1. Schreibt man @,(x) fur @(i, x), so gilt Do, = DW,') fur alle i . 2. Es gibt eine dreistellige allgemein-rekursive Funktion M mit '1 Mit D,, oder abkiimnd Di w i d der Dejinitionebereiclr der Funktion (pI bezeiohnet.