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

12

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ł.

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.

András Salamon
źródło
5
Chociaż skróty są znane wśród społeczności CS, chciałbym je rozwinąć dla „reszty z nas”: PH (Hierarchia czasu wielomianowego), SO (logika drugiego rzędu) i VO (logika zmiennego rzędu).
MS Dousti
1
W rzeczywistości nigdy wcześniej nie słyszałem o VO, więc dziękuję za wyjaśnienie.
Suresh Venkat
@Suresh: Tak, zapomniałem powiedzieć, że VO wcale nie jest dobrze znane. W każdym razie jesteś bardzo mile widziany!
MS Dousti
Jest tu ładna ilustracja różnych klas logiki i złożoności: cs.umass.edu/~immerman/descriptive_complexity.html , choć nie wspomina o VO.
MS Dousti
Być może nie byłem jasny: VO zostało zdefiniowane mniej niż dziesięć lat temu i nie jest dobrze znane. Interesuje mnie to, ponieważ jest to sposób na rozszerzenie logiki pierwszego rzędu, aby była bardziej wydajna, bez użycia operatorów o stałym punkcie.
András Salamon,

Odpowiedzi:

3

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.PHPNP

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.

AC0AC0cex

Kilka dodatkowych komentarzy:

AC0

Kaveh
źródło
4

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.

iXijYj(Xi=Yj)iXiiYi(Xi=Yi)iXiX

ϕ(i)iki>kϕ(i)kϕ(i)iϕ(i)i<kϕ(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.

Arthur MILCHIOR
źródło
Dzięki za dyskusję, przyjrzę się waszej przeformułowaniu. Czy masz jakieś sugestie dotyczące niektórych sposobów ograniczenia logiki, aby nie była ona tak potężna - czy byłoby coś takiego, jak wymaganie, aby niekwantowana część wzoru znajdowała się w CNF z klauzulami Horn, która byłaby użyteczna, tak jak ma to miejsce w przypadku klasycznych kwantyfikatorów?
András Salamon
Mówiąc ściślej, mam na myśli ograniczenie składniowe wzdłuż linii SNP, w którym kwantyfikatory SO są stosowane do formuły FO o określonej formie (dla SNP, tylko z uniwersalnymi kwantyfikatorami FO), a następnie stosuje się dalsze ograniczenia, takie jak Formuła FO wewnątrz kwantyfikatorów FO to Horn lub Krom. Ostatni akapit twojej sekcji 5.3 mówi o tym, ale nie rozumiem twojego komentarza, że ​​takie podejście jest problematyczne.
András Salamon,
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
2

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)

Arthur MILCHIOR
źródło
1
Dzięki za wgląd. To zdecydowanie wymaga dalszych przemyśleń!
András Salamon,