Teorie charakteryzujące klasy złożoności obliczeniowej

Czytając artykuł „ Teoria aplikacyjna dla FPH ”, można natknąć się na następujący fragment:

Biorąc pod uwagę teorie charakteryzujące klasy złożoności obliczeniowej, istnieją trzy różne podejścia:

• w jednym funkcje, które można zdefiniować w teorii, są „automatycznie” w ramach pewnej klasy złożoności. Na takim koncie należy ograniczyć składnię, aby zagwarantować, że pozostanie się w odpowiedniej klasie. Powoduje to na ogół problem polegający na tym, że niektóre definicje funkcji nie działają już, nawet jeśli funkcja należy do rozważanej klasy złożoności.
• Na drugim koncie podstawowa logika jest ograniczona.
• Na trzecim koncie nie ogranicza się składni, pozwalając na ogół zapisywać „warunki funkcji” dla funkcji arbitralnych (częściowo rekurencyjnych), ani logiki, ale tylko dla tych funkcji, które należą do rozważanej klasy złożoności , można udowodnić, że mają one pewną charakterystyczną właściwość, zwykle właściwość, że są „w sposób możliwy do udowodnienia ogółem”. Podczas gdy terminy funkcji, zgodnie z podstawową strukturą syntaktyczną, mogą mieć prosty charakter obliczeniowy, tj. Jako terminy , logika stosowana do udowodnienia właściwości charakterystycznej może być klasyczna.$\lambda$

Moje pytanie dotyczy odniesień, które mogą być wstępem do trzech wyżej wymienionych podejść. W tym fragmencie widzimy tylko charakterystykę podejść, ale czy mają one ogólnie przyjęte nazwy?

Myślę, że pierwsze podejście, ograniczone podejście arytmetyczne , jest najbardziej popularnym i dobrze zbadanym podejściem. Arytmetyka związana z nazwą wskazuje na użycie słabych podsystemów arytmetyki Peano, gdzie indukcja jest ograniczona do formuł z ograniczonymi kwantyfikatorami. W tym miejscu streściłem już główną ideę tego podejścia poście . Doskonałym niedawnym odniesieniem do ograniczonej arytmetyki jest książka Cooka i Nguyena, której szkic jest swobodnie dostępny.

Drugie podejście wykorzystuje logikę liniową i jej podsystem, o czym wspomniał Kaveh, o czym niewiele wiem.

Nie słyszałem o trzecim podejściu, chociaż pracuję nad ograniczoną arytmetyką. Ale wydaje mi się to trochę dziwne, ponieważ bez jakiejkolwiek formy ograniczenia składniowego lub logicznego, w jaki sposób teoria charakteryzuje klasę złożoności?

$W$$W$$C$$T$

• $f$$t_f$$T$$\forall x. W(x) \to W(t_f(x))$ wtedy i tylko wtedy gdy $f$ jest w $C$.

Pochodzą z prac Thomasa Strahma, w szczególności z następujących artykułów:

Thomas Strahm. Teorie o samozastosowaniu i złożoności obliczeniowej, Information and Computation 185, 2003, s. 263–297. http://dx.doi.org/10.1016/S0890-5401(03)00086-5

Thomas Strahm. Teoretyczna charakterystyka podstawowych możliwych funkcjonałów, Theoretical Computer Science 329, 2004, s. 159-176. http://dx.doi.org/10.1016/j.tcs.2004.08.009

Naprawdę nie wiem, czy jest reprezentatywny dla tego obszaru (z powodu mojej ogólnej nieznajomości z nim), ale praca Giorgi Japaridze nad logiką obliczalności należy do drugiego podejścia.