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

15

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?

Oleksandr Bondarenko
źródło
Podstawowym zagadnieniem złożoności obliczeniowej jest znalezienie teorii charakteryzującej wydajne obliczenia?
Mohammad Al-Turkistany
4
O pierwszym podejściu, które moim zdaniem jest głównym podejściem, możecie przeczytać w najnowszej książce Cooka i Nguyena: cs.toronto.edu/~sacook/homepage/book . Nie widziałem trzeciego podejścia (z mojego ograniczonego doświadczenia) i potrzebuję czasu, aby zrozumieć, co oznacza drugie podejście.
Dai Le
@Dai Le: Dziękuję za komentarz. Co powiesz na nazwę tego podejścia? Dowód złożoności?
Oleksandr Bondarenko
2
@Oleksandr: Myślę, że jest to podejście „ograniczonej arytmetyki”. To podejście jest bardzo dobrze zbadane i eleganckie. Książka Cooka-Nguyena zawiera również wskazówki do innych źródeł. Napisałem trochę o tym tutaj: cstheory.stackexchange.com/questions/3253/...
Dai Le
2
@Dai uczynić komentarz odpowiedzią?
Suresh Venkat

Odpowiedzi:

15

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?

Dai Le
źródło
7

W.W.doT.

  • fatfaT.x.W.(x)W.(tfa(x)) wtedy i tylko wtedy gdy fa jest w do.

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

Jan Johannsen
źródło
3

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.

Emil Jeřábek wspiera Monikę
źródło