模型論是數(shù)理邏輯中研究語(yǔ)義、語(yǔ)法、理論或公理系統(tǒng)與滿足該理論的模型之間相互關(guān)系的一個(gè)分支，考察的對(duì)象是語(yǔ)句或理論（語(yǔ)句集）與相應(yīng)的結(jié)構(gòu)（模型類(lèi)），以及它們之間的基本關(guān)系。早期的模型論側(cè)重于研究代數(shù)及數(shù)論結(jié)構(gòu)與理論，故有“模型論=邏輯+泛代數(shù)”之說(shuō)。隨后其研究與應(yīng)用的對(duì)象逐漸擴(kuò)充到數(shù)學(xué)的其他領(lǐng)域，如分析、概率、拓?fù)淠酥链鷶?shù)幾何等，也滲透進(jìn)了計(jì)算機(jī)科學(xué)。而計(jì)算機(jī)學(xué)科的發(fā)展對(duì)邏輯與模型論提出了許多挑戰(zhàn)性的問(wèn)題，刺激了后者的進(jìn)一步發(fā)展。特別是廣義的有限模型論，在80年代形成并急速發(fā)展起來(lái)，已在數(shù)據(jù)庫(kù)、計(jì)算復(fù)雜性以及形式語(yǔ)言與自動(dòng)機(jī)等理論中取得突出成果或重大的應(yīng)用。[1-2]
　　所謂“計(jì)算復(fù)雜性”，通常被定義為計(jì)算的機(jī)器模型所需要的資源。無(wú)法就一個(gè)個(gè)具體問(wèn)題去研究它的計(jì)算復(fù)雜性，但可以依據(jù)難度去研究各種計(jì)算問(wèn)題之間的聯(lián)系，按復(fù)雜性把問(wèn)題分成不同的類(lèi)，即復(fù)雜類(lèi)（Complexity Class）?，F(xiàn)在常用的度量標(biāo)準(zhǔn)主要是計(jì)算所需的步數(shù)或指令條數(shù)（時(shí)間復(fù)雜度），也有計(jì)算所需的存儲(chǔ)單元數(shù)量（空間復(fù)雜度）。
　　本文從研究模型論的思想和方法入手，對(duì)于計(jì)算機(jī)學(xué)科中的重要理論——計(jì)算復(fù)雜性，進(jìn)行了分析和研究，并分析和研究了計(jì)算復(fù)雜性和邏輯學(xué)在有限結(jié)構(gòu)上的關(guān)系，以及如何用模型論相關(guān)的理論和方法去獲取復(fù)雜問(wèn)題的復(fù)雜類(lèi)。
　　圖著色問(wèn)題是NP-難度的問(wèn)題。如著名的四色問(wèn)題[8-9]（四色猜想）是近代三大數(shù)學(xué)難題之一。在模型論中，我們用形式語(yǔ)言刻畫(huà)圖論，則圖論的語(yǔ)言L = { E}，這里的E表示“邊”，L的理論即圖論可以表示為兩個(gè)句子的集合：
　　1) (?x)(?y)