Czy istnieje naturalne ograniczenie logiki VO, która przechwytuje P lub NP?

Papier

• Lauri Hella i José María Turull-Torres, Obliczanie zapytań z logiką wyższego rzędu , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009

proponuje logikę VO, logikę zmiennego rzędu. Umożliwia to kwantyfikację zamówień ponad zmiennymi. VO jest dość potężny i może wyrażać niektóre zapytania, które nie są obliczalne. (Jak wskazał Arthur Milchior poniżej, faktycznie ujmuje całą hierarchię analityczną .) Autorzy pokazują, że fragment VO uzyskany przez dopuszczenie tylko ograniczonej uniwersalnej kwantyfikacji zmiennych zmiennych dokładnie wyraża wszystkie zapytania. VO pozwala, aby zmienne rzędu przekraczały liczby naturalne, więc ograniczenie zmiennych porządku jest oczywiście naturalnym warunkiem narzucenia.

Czy istnieje (ładny) fragment VO, który przechwytuje P lub NP?

Analogicznie, w klasycznej logice pierwszego rzędu, pozwalającej na kwantyfikację zbiorów obiektów, daje mocniejszą logikę zwaną logiką drugiego rzędu lub SO. SO przechwytuje całą hierarchię wielomianową ; jest to zwykle zapisane jako PH = SO. Istnieją ograniczone formy SO przechwytujące ważne klasy złożoności: NP = SO, P = SO-Horn, i NL = SO-Krom. Są one uzyskiwane przez nałożenie ograniczeń na składnię dozwolonych formuł.$\exists$

Istnieją więc proste sposoby ograniczenia SO w celu uzyskania interesujących klas. Chciałbym wiedzieć, czy istnieją podobne bezpośrednie ograniczenia VO, które są w przybliżeniu właściwym poziomem ekspresji dla P lub NP. Jeśli takie ograniczenia nie są znane, zainteresowałbym się sugestiami dla potencjalnych kandydatów lub niektórymi argumentami, dlaczego takie ograniczenia są mało prawdopodobne.

Sprawdziłem (kilka) artykułów, które cytują ten artykuł, i sprawdziłem oczywiste frazy w Google i Scholar, ale nie znalazłem nic, co byłoby oczywiste. Większość artykułów dotyczących logiki potężniejszej niż pierwszego rzędu nie wydaje się dotyczyć ograniczeń ograniczających moc do królestwa „rozsądnych” obliczeń, ale wydaje się, że z zadowoleniem mieszka w uniwersum klas arytmetycznych i analitycznych. Byłbym zadowolony ze wskaźnika lub nieoczywistej frazy do wyszukania; może to być dobrze znane osobie pracującej w logice wyższego rzędu.

Uwaga: To nie jest tak naprawdę odpowiedź na pytanie, to tylko niektóre komentarze opublikowane jako odpowiedź. :)

Zauważ, że w VO definiuje się zbiory nad zbiorem liczb naturalnych (podobne do zbiorów zdefiniowanych w teorii rekurencji), gdzie tak jak w opisowym ustawieniu złożoności (SO, -SO, SO-Horn) mówimy o strukturach skończonych. Formuła SO w dawnym otoczeniu nie da p h ale cała hierarchia analitycznych Arthur Milchior napisał w swojej odpowiedzi. IMHO, lepsze porównanie byłoby z ograniczonymi teoriami arytmetycznymi. Nie sądzę, że można uzyskać poniżej zestawów ce, chyba że wszystkie kwantyfikatory zostaną powiązane z domenami skończonymi, aby uzyskać P lub N P, rozmiar domen powinien być bardzo mały.$\exists$$PH$$P$$NP$

czy obecność jednego nieograniczonego kwantyfikatora wystarcza do przechwycenia zestawów ce?

Problem polega na tym, że prawdopodobnie chcesz, aby język nie zawierał dodatkowych symboli, takich jak równość, dodawanie, mnożenie (prawda?), Jeśli mielibyśmy je wtedy według twierdzenia MRDP, formuł diofantycznych (kwantyfikatory egzystencjalne pierwszego rzędu przed równością dwóch wielomianów) przechwytuje zestawy ce. Jeśli nie zezwalamy na te symbole w języku, problem jest bardziej skomplikowany, można użyć kwantyfikatorów wyższego rzędu, aby je zdefiniować, ale zwiększyłoby to złożoność kwantyfikatora. Więc jeśli chcę udzielić krótkiej odpowiedzi na pytanie dotyczące jednego kwantyfikatora, nie wiem.

$AC^0$$AC^0$$c$$e$$x$

Kilka dodatkowych komentarzy:

$AC^0$

Aby uzyskać informacje, VO jest w rzeczywistości naprawdę potężniejsze niż to, co podajesz; zawiera całą hierarchię analityczną (stąd też całą hierarchię arytmetyczną). Wynik nie został opublikowany, ani przesłany w żadne miejsce, ale można go znaleźć na mojej stronie, www.milchior.fr/ho.pdf sekcja 7 strona 47.

$\forall i \forall X^i\forall j\exists Y^j (X^i=Y^j)$$\forall i \forall X^i\forall i\exists Y^i (X^i=Y^i)$$i$$X$$^i$$X$

$\phi(i)$$i$$k$$i>k$$\phi(i)$$k$$\phi(i)$$\forall i \phi(i)$$\forall i < k \phi(i)$

W przeciwnym razie możesz z pewnością ograniczyć VO, ograniczając maksymalne przyjęte zamówienie; ale wtedy otrzymujesz język „wyższego rzędu” (HO) i prawdopodobnie nie tego chcesz.

Aby odpowiedzieć na twój komentarz, myślę, że powinienem udzielić kolejnej odpowiedzi, mówiąc tylko o Kromie i Hornu (być może powinienem zadać pytanie na te pytania CSTheory)

Sugeruję przeczytanie sekcji 5.3 strony 34 mojego artykułu na temat problemu, który napotkałem na temat Horn i Krom w logice wysokiego porządku. Ten sam problem napotkasz w Zmiennym Porządku (który jest wyraźnie nadzbiorem Wysokiego Porządku).

Nie wiem, czy zwróciłeś na to uwagę, ale SO (krom) jest równe P, gdy pierwsze zamówienie jest uniwersalne; rzeczywiście możesz wyrazić problem NP-zupełny, jeśli dodasz istniejącą zmienną pierwszego rzędu. (Nie pamiętam przykładu, który miałem wcześniej, mogę spróbować go przeszukać, jeśli chcesz)

Nie wiem, czym stałaby się ta składniowa resctriction dla logiki wysokiego lub zmiennego rzędu ... chodzi mi o to, że powinieneś również pomyśleć o dobrym sposobie ograniczania kwantyfikatorów, ponieważ samo ograniczanie części wolnej od kwantyfikatora nie jest przydatne ( przynajmniej dla formuł Krom)