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.
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?
cc.complexity-theory
reference-request
complexity-classes
lo.logic
proof-complexity
Oleksandr Bondarenko
źródło
źródło
Odpowiedzi:
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?
źródło
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
źródło
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.
źródło