Gibt es eine natürliche Einschränkung der VO-Logik, die P oder NP erfasst?

Das Papier

• Lauri Hella und José María Turull-Torres, Berechnen von Abfragen mit Logik höherer Ordnung , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009

schlägt Logik VO vor, Logik variabler Ordnung. Dies ermöglicht eine Quantifizierung über Ordnungen über die Variablen. VO ist ziemlich leistungsfähig und kann einige nicht berechenbare Abfragen ausdrücken. (Wie Arthur Milchior weiter unten ausführt, erfasst es tatsächlich die gesamte analytische Hierarchie .) Die Autoren zeigen, dass das Fragment von VO, das durch Erlauben einer nur begrenzten universellen Quantifizierung über die Ordnungsvariablen erhalten wird, alle ce-Abfragen genau ausdrückt. VO ermöglicht es den Ordnungsvariablen, sich über die natürlichen Zahlen zu erstrecken, so dass die Begrenzung der Ordnungsvariablen eindeutig eine natürliche Bedingung ist, die auferlegt werden muss.

Gibt es ein (nettes) Fragment von VO, das P oder NP erfasst?

Analog dazu ergibt sich in der klassischen Logik erster Ordnung, die eine Quantifizierung über Objektmengen ermöglicht, eine leistungsfähigere Logik, die als Logik zweiter Ordnung oder SO bezeichnet wird. SO erfasst die gesamte Polynomhierarchie ; Dies wird normalerweise als PH = SO geschrieben. Es gibt eingeschränkte Formen von SO wichtig Komplexitätsklassen erfassen: NP = SO, P = SO-Horn, und NL = SO-Krom. Diese erhalten Sie, indem Sie die Syntax zulässiger Formeln einschränken.$\exists$

Es gibt also einfache Möglichkeiten, SO einzuschränken, um interessante Klassen zu erhalten. Ich würde gerne wissen, ob es ähnliche direkte Einschränkungen für VO gibt, die in etwa der richtigen Expressivität für P oder NP entsprechen. Wenn solche Einschränkungen nicht bekannt sind, wäre ich an Vorschlägen für wahrscheinliche Kandidaten oder an einigen Argumenten interessiert, warum solche Einschränkungen unwahrscheinlich sind.

Ich habe die (wenigen) Papiere, in denen dieser Artikel zitiert wird, und die offensichtlichen Redewendungen bei Google und Scholar überprüft, aber nichts offensichtlich Relevantes gefunden. Die meisten Arbeiten, die sich mit Logik befassen, die leistungsfähiger ist als die der ersten Ordnung, scheinen sich nicht mit Einschränkungen zu befassen, um die Leistung in den Bereich "vernünftiger" Berechnungen zu bringen, sondern scheinen sich mit dem Universum der arithmetischen und analytischen Klassen zu beschäftigen. Ich würde mich über einen Zeiger oder einen nicht offensichtlichen Suchbegriff freuen. Dies könnte jemandem bekannt sein, der in Logik höherer Ordnung arbeitet.

Hinweis: Dies beantwortet die Frage nicht wirklich. Dies sind nur einige Kommentare, die als Antwort gepostet wurden. :)

Beachten Sie, dass in VO, man setzt auf die Menge der natürlichen Zahlen (ähnlich Sets definiert in Rekursionstheorie) definieren , wo , wie in der beschreibenden Komplexität Einstellung (SO, SO, SO-Horn) wir über endlichen Strukturen sprechen. Eine SO Formel in der früheren Einstellung gibt nicht P H , sondern die ganze analytische Hierarchie als Arthur Milchior in seiner Antwort geschrieben hat. Meiner Meinung nach wäre ein besserer Vergleich mit beschränkten arithmetischen Theorien. Ich glaube nicht, dass Sie unter ce Mengen kommen können, wenn Sie nicht alle Quantifizierer an endliche Domänen gebunden haben. Um P oder N P zu erhalten, sollte die Größe der Domänen sehr klein sein.$\exists$$PH$$P$$NP$

Reicht das Vorhandensein eines unbeschränkten Quantifizierers aus, um CESets zu erfassen?

Das Problem ist, dass Sie wahrscheinlich möchten, dass die Sprache keine zusätzlichen Symbole wie Gleichheit, Addition, Multiplikation enthält (richtig?), Wenn wir sie dann nach MRDP-Theorem, diophantinischen Formeln (Existenzquantifikatoren erster Ordnung vor einer Gleichheit von zwei Polynomen) hatten. würde ce Sätze erfassen. Wenn wir diese Symbole in der Sprache nicht zulassen, ist das Problem komplizierter. Man kann Quantifizierer höherer Ordnung verwenden, um sie zu definieren, aber das würde die Quantifiziererkomplexität erhöhen. Wenn ich Ihre Frage zu einem einzelnen Quantifizierer kurz beantworten möchte, weiß ich es nicht.

Wenn wir -Relationen in der Sprache ausdrücken können , dann würde ein einzelner unbegrenzter existentieller Quantifizierer ausreichen, um ce-Mengen zu erfassen. Der Grund dafür ist, dass A C 0 überprüfen kann, ob ein String c die Berechnung eines TM ist$AC^0$$AC^0$$c$$e$$x$ . Durch Polynome begrenzte Formeln erster Ordnung in Gegenwart von Gleichheit, Addition und Multiplikation erfassen PH. Wenn wir sie also in der Sprache haben, ist die Antwort positiv, aber wie gesagt, Sie suchen wahrscheinlich nach einer Sprache ohne diese Symbole.

Einige zusätzliche Kommentare:

Angenommen, wir haben eine VO-Einschränkung, die mindestens A C 0 ausdrücken kann$AC^0$ . Dann ergibt ein einzelner unbegrenzter existentieller Quantifizierer des Zahlentyps vor diesen eingeschränkten Formeln die gesamten ce-Mengen.

Zur Information, VO ist in der Tat wirklich mächtiger als das, was Sie angeben. es enthält die gesamte analytische Hierarchie (daher auch die gesamte arithmetische Hierarchie). Das Ergebnis wird weder veröffentlicht noch an irgendeinen Ort übermittelt, aber Sie finden es auf meiner Seite, www.milchior.fr/ho.pdf, Abschnitt 7, Seite 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)$ ist wahr, was bedeutet, dass$i$$X$$^i$$X$ .

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

Andernfalls können Sie VO mit Sicherheit einschränken, indem Sie die maximal akzeptierte Reihenfolge einschränken. Aber dann erhalten Sie eine Sprache "höherer Ordnung" (HO), und dies ist wahrscheinlich nicht das, was Sie wollen.

Um auf Ihren Kommentar zu antworten, sollte ich wohl eine andere Antwort geben und nur über Krom und Horn sprechen (möglicherweise sollte ich CSTheory eine Frage dazu stellen).

Ich schlage vor, dass Sie Abschnitt 5.3, Seite 34 meines Aufsatzes über das Problem lesen, das ich bei Horn und Krom in der Logik hoher Ordnung kennengelernt habe. Sie werden das gleiche Problem in Variable Order (was eindeutig eine Obermenge von High Order ist) treffen.

Ich weiß nicht, ob Sie darauf geachtet haben, aber SO (krom) ist gleich P, wenn die erste Ordnung universell ist; In der Tat können Sie ein NP-vollständiges Problem ausdrücken, wenn Sie eine existierende Variable erster Ordnung hinzufügen. (Ich erinnere mich nicht an das Beispiel, das ich vorher hatte. Ich kann versuchen, es zu suchen, wenn Sie es wollen.)

Ich weiß nicht, was diese syntaktische Einschränkung für eine Logik höherer oder variabler Ordnung bedeuten würde. Mein Punkt ist nur, dass Sie sich auch eine gute Möglichkeit überlegen sollten, Quantifizierer einzuschränken, da es nicht sinnvoll ist, den quantifiziererfreien Teil allein einzuschränken ( zumindest für Krom-Formeln)