描述性複雜性理論

描述性複雜性是計算複雜性理論和有限模型理論的一個分支，它通過表達其語言所需的邏輯類型來表徵複雜性類別。例如， pH是多項式層次結構中所有復雜性類的結合，正是通過二階邏輯語句表達的語言類。複雜性與有限結構的邏輯之間的這種聯繫允許將結果輕鬆從一個區域轉移到另一個區域，從而促進了新的證明方法，並提供了其他證據表明主要的複雜性類別是“自然”的，而不是與所使用的特定抽像機器相關的。定義它們。

具體而言，每個邏輯系統都會在其中產生一組可表達的查詢。當限制有限結構時，這些查詢與傳統複雜性理論的計算問題相對應。

描述性複雜性的第一個主要結果是Ronald Fagin在1974年顯示的Fagin定理。它確定NP正是通過存在的二階邏輯句子表達的一組語言。也就是說，二階邏輯不包括對關係，函數和子集的通用量化。後來，許多其他課程以這種方式進行了特徵。

那個設定

當我們使用邏輯形式主義描述一個計算問題時，輸入是有限的結構，該結構的要素是話語的領域。通常，輸入是（位的位或字母上）的字符串，邏輯結構的元素表示字符串的位置，或者輸入是圖形，邏輯結構的元素代表其頂點。輸入的長度將通過各自結構的大小來衡量。無論結構是什麼，我們都可以假設可以測試有關係，例如且僅當從x到y的邊緣（如果結構為圖形）或”時是正確的。 當且僅當字符串的n字母為1時，是真的在圖中檢查可及性，我們將不得不選擇兩個常數S （start）和t （終端）。

在描述性複雜性理論中，我們經常假設元素上有一個總順序，並且我們可以檢查元素之間的平等。這使我們可以將元素視為數字：元素x表示數字n ，並且僅當存在元素與 。因此，我們也可能具有原始的謂詞“位” 如果只有x的二進制擴展的k thit是1。（我們可以用三元關係代替加法和乘法當且僅當和當且僅當 ）。

概述複雜性類的特徵

如果我們將自己限制為具有後繼關係和基本算術謂詞的有序結構，那麼我們將獲得以下特徵：

  • 一階邏輯定義了AC 0類，即有界深度的多項式大小電路所識別的語言，這等於在恆定時間內通過並發隨機訪問機識別的語言。
  • 一階邏輯以對稱或確定性的及時閉合操作員的形式增強，產生L ，在對數空間中可解決的問題。
  • 帶有及時閉合操作員的一階邏輯產生NL ，在非確定對數空間中可以解決的問題。
  • 具有最小固定點運算符的一階邏輯給出了P ，可以在確定性多項式時間中解決的問題。
  • 存在二階邏輯產生NP 。
  • 通用二階邏輯（不包括存在的二階定量）會產生Co-NP 。
  • 二階邏輯對應於多項式層次結構pH 。
  • 二階邏輯具有及傳遞性閉合（無論是交換是否），可產生PSPACE ，這些問題可以在多項式空間中解決。
  • 帶有最小固定點運算符的二階邏輯給出了exptime ，這些問題可以在指數時間內解決。
  • ho ，由高階邏輯定義的複雜性類別等於基本

亞物質時間

沒有任何操作員

在電路複雜性中，具有任意謂詞的一階邏輯可以證明等於AC 0 ，即交流層次結構中的第一類。確實，從fo的符號到電路節點有自然的翻譯， 存在和大小n 。具有算術謂詞的簽名中的一階邏輯表明，AC 0電路家族的限制是在交替的對數時間中可構建的電路家族。僅具有順序關係的簽名中的一階邏輯對應於一組無星語。

傳遞閉合邏輯

當一階邏輯與計算二進制關係的傳遞閉合的操作員增強時，它的表達能力大大獲得。已知所得的傳遞閉合邏輯表徵有序結構上的非確定性對數空間（NL） 。 Immerman使用了這一點，以表明NL在補充下是封閉的（即NL = Co-NL）。

當限制傳遞閉合操作員以確定性及其性閉合時，所得邏輯恰好表徵有序結構上的對數空間。

二階Krom公式

在具有後繼函數的結構上，NL也可以通過二階Krom公式來表徵。

So-krom是一組布爾的查詢集，可定義的二階公式以結合性正常形式定義，因此一階量化器是通用的，並且該公式的無量詞為krom形式，這意味著一階公式是析取的結合，在每個“分離”中，最多都有兩個變量。每個二階Krom公式都等效於存在的二階Krom公式。

So-krom表徵了具有後繼函數的結構上的NL。

多項式時間

在有序結構上，一階最小固定點邏輯捕獲了ptime ：

一階最少定點邏輯

FO [LFP]是由最少固定點運算符的一階邏輯擴展，它表達了單調表達式的固定點。這增加了具有表達遞歸的能力的一階邏輯。由Immerman和Vardi獨立顯示的Immerman -Vardi定理表明，FO [LFP]在有序結構上表徵了ptime。

截至2022年，是否有自然邏輯在無序結構上表徵ptime。

AbiteBoul – Vianu定理指出，當且僅當Fo [lfp] = fo [pfp]時，所有結構上的fo [lfp] = fo [pfp];因此，只有且僅當P = pspace。該結果已擴展到其他固定點。

二階喇叭公式

在存在後繼函數的情況下，Ptime也可以通過二階角公式來表徵。

So-horn是一組布爾的查詢集，可定義為脫節的正常形式的公式，因此一階量化器都是通用的，並且該公式的無量詞的部分為號角，這意味著它是一個大的，並且是一個大的，或者，在每個變量中，除一個變量外，都可能被否定。

該類等於具有後繼功能的結構上的P。

這些公式可以轉化為存在二階喇叭邏輯中的預先公式。

非確定性多項式時間

Fagin的定理

羅納德·法金（Ronald Fagin）的1974年證據表明，複雜性類NP的特徵是在存在的二階邏輯中可公理化的結構類別是描述性複雜性理論的起點。

由於存在公式的補充是通用公式，因此立即遵循Co-NP的特徵是通用二階邏輯。

因此，不受限制的二階邏輯等於多項式層次結構pH 。更確切地說，我們對Fagin定理的概括：PRENEX正常形式中的公式集，其中二階和二階的普遍量化符交替k次k Times的k Th級k th級別的k Th級別。

與大多數複雜性類別的其他特徵不同，Fagin的定理及其概括並不能以結構的總訂購為前提。這是因為存在二階邏輯本身足以表達使用二階變量在結構上的可能總訂單。

超越NP

部分固定點是Pspace

可以在多項式空間（ PSPACE）中計算的所有問題的類別，可以通過使用更具表現力的部分固定點運算符來增強一階邏輯來表徵。

部分固定點邏輯FO [PFP]是使用部分固定點運算符的一階邏輯的擴展，如果有一個公式，則表示公式的固定點，否則將返回“ false”。

部分固定點邏輯表徵有序結構上的pspace 。

傳遞閉合是pspace

二階邏輯可以通過與一階邏輯相同的方式擴展，從而導致SO [TC]。 TC運算符現在還可以將二階變量作為參數。因此，[TC]表徵了Pspace 。由於可以用二階邏輯引用排序，因此該表徵不會以排序的結構為前提。

基本功能

基本功能的時間複雜性類別可以通過HO來表徵，HO是可以通過高階邏輯公式識別的結構的複雜性類別。高階邏輯是具有高階量詞的一階邏輯和二階邏輯的擴展。在秩序和非確定性算法的時間是由指數水平。

定義

我們定義高階變量。訂單變量有一個Arity 並代表任何一組 - 秩序元素的元素 。它們通常用上案例編寫，並且具有自然數字作為指示命令的指數。高階邏輯是一組一階公式，我們在高階變量上添加定量；因此，我們將使用FO文章中定義的術語，而無需再次定義它們。

何是最多有訂單變量的公式集 。何是形式公式的子集 ， 在哪裡是量詞和意思是是訂單變量的元組具有相同的量化。所以是一組公式訂單量詞的交替 ， 以。。。開始 ，然後是秩序公式 。

使用四分法的標準符號， 和 。 和時代

正常形式

每個秩序公式這等同於Prenex正常形式的公式訂單，然後是訂單公式以正常形式。

與復雜性類別的關係

HO等於基本功能的類基本。更確切地說 ，意思是一座塔 2s，以 ， 在哪裡是常數。一個特殊情況是 ，這正是Fagin的定理。在多項式層次結構中使用Oracle機器，