ความซับซ้อนเชิงพรรณนาเป็นสาขาหนึ่งของทฤษฎีความซับซ้อนเชิงคำนวณและทฤษฎีแบบจำลองจำกัดที่อธิบายคลาสความซับซ้อนโดยประเภทของตรรกะที่จำเป็นในการแสดงภาษาในคลาสเหล่านั้น^{[ 1 ]}ตัวอย่างเช่นPHซึ่งเป็นการรวมกันของคลาสความซับซ้อนทั้งหมดในลำดับชั้นพหุนาม เป็นคลาสของภาษาที่สามารถแสดงได้ด้วยข้อความของตรรกะลำดับที่สองการเชื่อมโยงระหว่างความซับซ้อนและตรรกะของโครงสร้างจำกัดนี้ทำให้สามารถถ่ายโอนผลลัพธ์จากพื้นที่หนึ่งไปยังอีกพื้นที่หนึ่งได้อย่างง่ายดาย อำนวยความสะดวกวิธีการพิสูจน์ใหม่ ๆ และให้หลักฐานเพิ่มเติมว่าคลาสความซับซ้อนหลักนั้น "เป็นธรรมชาติ" และไม่ได้ผูกติดกับเครื่องจักรนามธรรม เฉพาะ ที่ใช้ในการกำหนดคลาสเหล่านั้น

โดยเฉพาะอย่างยิ่ง ระบบตรรกะแต่ละ ระบบ จะสร้างชุดคำถามที่สามารถแสดงออกมาได้ในระบบนั้น คำถามเหล่านั้น – เมื่อจำกัดให้อยู่ในโครงสร้างที่มีจำนวนจำกัด – จะสอดคล้องกับปัญหาการคำนวณของทฤษฎีความซับซ้อนแบบดั้งเดิม

ผลลัพธ์หลักประการแรกของความซับซ้อนเชิงพรรณนาคือทฤษฎีบทของเฟกินซึ่งแสดงโดยโรนัลด์ เฟกินในปี 1974 ทฤษฎีบทนี้ระบุว่าNPคือเซตของภาษาที่สามารถแสดงได้ด้วยประโยคของตรรกะลำดับที่สอง แบบมีอยู่จริง กล่าวคือ ตรรกะลำดับที่สองที่ไม่รวมการกำหนดปริมาณแบบสากลเหนือความสัมพันธ์ฟังก์ชันและเซตย่อยต่อมามีการกำหนดลักษณะของคลาสอื่นๆ อีกมากมายในลักษณะเดียวกันนี้

เมื่อเราใช้รูปแบบตรรกะเพื่ออธิบายปัญหาการคำนวณ ข้อมูลที่ป้อนเข้าจะเป็นโครงสร้างจำกัด และองค์ประกอบของโครงสร้างนั้นจะเป็นโดเมนของการพิจารณาโดยปกติแล้ว ข้อมูลที่ป้อนเข้าจะเป็นสตริง (ของบิตหรือตัวอักษร) และองค์ประกอบของโครงสร้างตรรกะจะแสดงตำแหน่งของสตริง หรือข้อมูลที่ป้อนเข้าจะเป็นกราฟ และองค์ประกอบของโครงสร้างตรรกะจะแสดงถึงจุดยอดของกราฟ ความยาวของข้อมูลที่ป้อนเข้าจะวัดจากขนาดของโครงสร้างนั้นๆ ไม่ว่าโครงสร้างจะเป็นอย่างไร เราสามารถสมมติได้ว่ามีความสัมพันธ์ที่สามารถทดสอบได้ ตัวอย่างเช่น " เป็นจริงก็ต่อเมื่อมีเส้นเชื่อมจากxไปยังy " (ในกรณีที่โครงสร้างเป็นกราฟ) หรือ " เป็นจริงก็ต่อเมื่อ ตัวอักษรตัวที่ nของสตริงเป็น 1" ความสัมพันธ์เหล่านี้คือภาคแสดงสำหรับระบบตรรกะอันดับหนึ่ง นอกจากนี้เรายังมีค่าคงที่ ซึ่งเป็นองค์ประกอบพิเศษของโครงสร้างนั้นๆ ตัวอย่างเช่น หากเราต้องการตรวจสอบการเข้าถึงได้ในกราฟ เราจะต้องเลือกค่าคงที่สองค่าคือs (จุดเริ่มต้น) และt (จุดสิ้นสุด) ${\displaystyle E(x,y)}$${\displaystyle P(n)}$

ในทฤษฎีความซับซ้อนเชิงพรรณนา เรามักจะสมมติว่ามีลำดับสมบูรณ์เหนือองค์ประกอบต่างๆ และเราสามารถตรวจสอบความเท่าเทียมกันระหว่างองค์ประกอบได้ สิ่งนี้ทำให้เราสามารถพิจารณาองค์ประกอบต่างๆ เป็นตัวเลขได้ กล่าวคือ องค์ประกอบxแทนตัวเลขnก็ต่อเมื่อมีองค์ประกอบy ที่มีคุณสมบัติ n ด้วยเหตุนี้ เราจึงอาจมีตัวบ่งชี้พื้นฐาน "บิต" ได้ โดยที่เป็นจริงก็ต่อเมื่อ บิตที่ kของการขยายเลขฐานสองของxเป็น 1 เท่านั้น (เราสามารถแทนที่การบวกและการคูณด้วยความสัมพันธ์แบบไตรภาคได้ เช่นเป็นจริงก็ต่อเมื่อ n = 1 และเป็นจริงก็ต่อเมื่อ n = 1 ) ${\displaystyle (n-1)}$${\displaystyle y<x}$${\displaystyle bit(x,k)}$${\displaystyle plus(x,y,z)}$${\displaystyle x+y=z}$${\displaystyle times(x,y,z)}$${\displaystyle x*y=z}$

หากเราจำกัดตัวเองอยู่เฉพาะโครงสร้างที่มีลำดับความสัมพันธ์แบบผู้สืบทอดและ述语ทางคณิตศาสตร์พื้นฐาน เราจะได้ลักษณะเฉพาะดังต่อไปนี้:

• ตรรกะลำดับแรกกำหนดคลาสAC ⁰ซึ่งเป็นภาษาที่รับรู้โดยวงจรขนาดพหุนามที่มีความลึกจำกัด ซึ่งเท่ากับภาษาที่รับรู้โดยเครื่องเข้าถึงแบบสุ่มพร้อมกันในเวลาคงที่^{[ 2 ]}
• ตรรกะลำดับแรกที่เสริมด้วยตัวดำเนินการปิด แบบสมมาตรหรือแบบกำหนดได้จะให้ผลลัพธ์เป็น Lซึ่งเป็นปัญหาที่สามารถแก้ไขได้ในพื้นที่ลอการิทึม^{[ 3 ]}
• ตรรกะลำดับแรกที่มี ตัวดำเนิน การปิดแบบส่งผ่านจะให้ผลลัพธ์เป็นNLซึ่งเป็นปัญหาที่สามารถแก้ไขได้ในพื้นที่ลอการิทึมแบบไม่กำหนด^{[ 4 ]}
• ตรรกะลำดับแรกที่มี ตัวดำเนินการ จุดตรึงน้อยที่สุดจะให้Pซึ่งเป็นปัญหาที่สามารถแก้ไขได้ในเวลาพหุนามเชิงกำหนดแต่เฉพาะบนโครงสร้างที่เรียงลำดับเท่านั้น^{[ 4 ]}
• ตรรกะลำดับที่สองเชิงการดำรงอยู่ให้ผลลัพธ์เป็นNP ^{[ 4 ]}
• ตรรกะลำดับที่สองสากล (ไม่รวมการกำหนดปริมาณลำดับที่สองแบบมีอยู่จริง) ก่อให้เกิดco- NP ^{[ 5 ]}
• ตรรกะ ลำดับที่สองสอดคล้องกับลำดับชั้นพหุนาม PH ^{[ 4 ]}
• ตรรกะลำดับที่สองที่มี ตัวดำเนิน การปิดแบบส่งผ่าน (สลับที่ได้หรือไม่ได้) ทำให้เกิดPSPACEซึ่งเป็นปัญหาที่สามารถแก้ไขได้ในพื้นที่พหุนาม^{[ 6 ]}
• ตรรกะลำดับที่สองที่มี ตัวดำเนินการ จุดคงที่น้อยที่สุดจะให้EXPTIMEซึ่งเป็นปัญหาที่สามารถแก้ไขได้ในเวลาเลขชี้กำลัง^{[ 7 ]}
• HOซึ่งเป็นคลาสความซับซ้อนที่กำหนดโดยตรรกะลำดับสูงเท่ากับELEMENTARY ^{[ 8 ]}

ในความซับซ้อนของวงจรตรรกะลำดับที่หนึ่งที่มีภาคแสดงใดๆ สามารถแสดงให้เห็นว่าเท่ากับAC ⁰ซึ่งเป็นคลาสแรกใน ลำดับชั้น ACอันที่จริง มีการแปลตามธรรมชาติจากสัญลักษณ์ของ FO ไปยังโหนดของวงจร โดยที่และมีขนาดnตรรกะลำดับที่หนึ่งในลายเซ็นที่มีภาคแสดงทางคณิตศาสตร์แสดงลักษณะเฉพาะของการจำกัดตระกูลวงจร AC ⁰เฉพาะวงจรที่สามารถสร้างได้ในเวลาลอการิทึมสลับ [ ^{2 ] ตรรกะ}ลำดับที่หนึ่งในลายเซ็นที่มีความสัมพันธ์ลำดับเพียงอย่างเดียวสอดคล้องกับเซตของ ภาษา ที่ปราศจากดาว^{[ 9 ] [ 10 ]}${\displaystyle \forall ,\exists }$${\displaystyle \land }$${\displaystyle \lor }$

ตรรกะลำดับแรกได้รับพลังการแสดงออกเพิ่มขึ้นอย่างมากเมื่อเสริมด้วยตัวดำเนินการที่คำนวณการปิดแบบส่งผ่านของความสัมพันธ์ทวิภาคตรรกะการปิดแบบส่งผ่าน ที่ได้นั้น เป็นที่ทราบกันดีว่าสามารถกำหนดลักษณะของปริภูมิลอการิทึมที่ไม่กำหนด (NL) บนโครงสร้างที่เรียงลำดับได้ Immermanใช้สิ่งนี้เพื่อแสดงว่า NL ปิดภายใต้ส่วนเติมเต็ม (กล่าวคือ NL = co-NL) ^{[ 11 ]}

เมื่อจำกัดตัวดำเนินการปิดแบบส่งผ่านให้เป็นการปิดแบบส่งผ่านเชิงกำหนดผลลัพธ์เชิงตรรกะจะแสดงลักษณะเฉพาะของปริภูมิเชิงลอการิทึมบนโครงสร้างเรียงลำดับ ได้อย่างแม่นยำ

ในโครงสร้างที่มีฟังก์ชันสืบทอด NL ยังสามารถกำหนดลักษณะได้ด้วยสูตร Krom อันดับ สอง

SO-Krom คือเซตของคำถามเชิงบูลีนที่สามารถนิยามได้ด้วยสูตรลำดับที่สองในรูปแบบปกติแบบเชื่อมโยงโดยที่ตัวบ่งปริมาณลำดับแรกเป็นแบบสากล และส่วนที่ไม่มีตัวบ่งปริมาณของสูตรอยู่ในรูปแบบ Krom ซึ่งหมายความว่าสูตรลำดับแรกเป็นการเชื่อมโยงของการแยก และในแต่ละ "การแยก" จะมีตัวแปรไม่เกินสองตัว ทุกสูตร Krom ลำดับที่สองเทียบเท่ากับสูตร Krom ลำดับที่สองแบบมีอยู่จริง

SO-Krom ระบุลักษณะ NL บนโครงสร้างที่มีฟังก์ชันสืบทอด^{[ 12 ]}

ในโครงสร้างที่มีลำดับ ตรรกะจุดตรึงน้อยที่สุดอันดับแรกสามารถจับภาพPTIME ได้ :

FO[LFP] คือส่วนขยายของตรรกะลำดับที่หนึ่งโดยตัวดำเนินการจุดตรึงน้อยที่สุด ซึ่งแสดงจุดตรึงของนิพจน์โมโนโทน สิ่งนี้เสริมตรรกะลำดับที่หนึ่งด้วยความสามารถในการแสดงการเรียกซ้ำ ทฤษฎีบท Immerman–Vardi ซึ่งแสดงโดยImmermanและVardi อย่างอิสระ แสดงให้เห็นว่า FO[LFP] มีลักษณะเฉพาะของ PTIME บนโครงสร้างที่มีลำดับ^{[ 13 ] [ 14 ]}

ณ ปี 2025 ยังคงเป็นที่ถกเถียงกันอยู่ว่ามีตรรกะธรรมชาติใดที่สามารถอธิบาย PTIME บนโครงสร้างที่ไม่เรียงลำดับได้หรือไม่

ทฤษฎีบทAbiteboul–Vianuระบุว่า FO[LFP]=FO[PFP] บนโครงสร้างทั้งหมดก็ต่อเมื่อ FO[LFP]=FO[PFP] เท่านั้น ดังนั้นก็ต่อเมื่อ P=PSPACE เท่านั้น ผลลัพธ์นี้ได้รับการขยายไปยังจุดตรึงอื่นๆ^{[ 7 ]}

ในกรณีที่มีฟังก์ชันสืบทอด PTIME สามารถอธิบายได้ด้วยสูตร Horn อันดับสองเช่นกัน

SO-Horn คือเซตของคำถามเชิงบูลีนที่สามารถกำหนดได้ด้วยสูตร SO ในรูปแบบปกติแบบแยกส่วนโดยที่ตัวบ่งปริมาณลำดับแรกทั้งหมดเป็นแบบสากล และส่วนที่ไม่มีตัวบ่งปริมาณของสูตรอยู่ใน รูปแบบ Hornซึ่งหมายความว่ามันคือ AND ขนาดใหญ่ของ OR และในแต่ละ "OR" ตัวแปรทุกตัวยกเว้นอาจจะมีเพียงตัวเดียวที่ถูกปฏิเสธ

คลาสนี้เท่ากับPบนโครงสร้างที่มีฟังก์ชันสืบทอด^{[ 15 ]}

สูตรเหล่านั้นสามารถแปลงเป็นสูตรพรีเน็กซ์ในตรรกะฮอร์นลำดับที่สองแบบมีอยู่จริงได้^{[ 12 ]}

การพิสูจน์ของ Ronald Fagin ในปี 1974 ที่ว่าคลาสความซับซ้อน NP มีลักษณะเฉพาะโดยคลาสของโครงสร้างที่สามารถกำหนดสัจพจน์ได้ในตรรกะลำดับที่สองแบบมีอยู่จริงนั้นเป็นจุดเริ่มต้นของทฤษฎีความซับซ้อนเชิงพรรณนา^{[ 5 ] [ 16 ]}

เนื่องจากส่วนเติมเต็มของสูตรการมีอยู่คือสูตรสากล จึงสรุปได้ทันทีว่า co-NP มีลักษณะเฉพาะด้วยตรรกะลำดับที่สองสากล^{[ 5 ]}

ดังนั้น ตรรกะลำดับที่สองที่ไม่จำกัด จึงเท่ากับลำดับชั้นพหุนาม PHกล่าวโดยละเอียด เรามีการวางนัยทั่วไปของทฤษฎีบทของ Fagin ดังนี้: เซตของสูตรในรูปแบบปกติ prenex ซึ่งตัวบ่งปริมาณเชิงมีอยู่และเชิงสากลของลำดับที่สองสลับกันkครั้ง บ่งบอกถึง ระดับที่ kของลำดับชั้นพหุนาม^{[ 17 ]}

แตกต่างจากลักษณะเฉพาะอื่นๆ ของคลาสความซับซ้อน ทฤษฎีบทของเฟกินและการวางนัยทั่วไปของทฤษฎีบทนี้ไม่ได้ตั้งสมมติฐานเกี่ยวกับการเรียงลำดับทั้งหมดบนโครงสร้าง นี่เป็นเพราะตรรกะลำดับที่สองแบบมีอยู่จริงนั้นสามารถแสดงออกได้เพียงพอที่จะอ้างถึงลำดับทั้งหมดที่เป็นไปได้บนโครงสร้างโดยใช้ตัวแปรลำดับที่สอง^{[ 18 ]}

กลุ่มของปัญหาทั้งหมดที่สามารถคำนวณได้ในปริภูมิพหุนามPSPACEสามารถอธิบายได้โดยการเสริมตรรกะอันดับหนึ่งด้วยตัวดำเนินการจุดตรึงบางส่วนที่มีความสามารถในการแสดงออกมากขึ้น

ตรรกะจุดตรึงบางส่วน (Partial fixed-point logic , FO[PFP]) คือส่วนขยายของตรรกะลำดับที่หนึ่งที่มีตัวดำเนินการจุดตรึงบางส่วน ซึ่งจะแสดงจุดตรึงของสูตรหากมี และส่งคืนค่า 'เท็จ' หากไม่มี

ตรรกะจุดตรึงบางส่วนเป็นลักษณะเฉพาะของPSPACEบนโครงสร้างเรียงลำดับ^{[ 19 ]}

ตรรกะลำดับที่สองสามารถขยายได้ด้วยตัวดำเนินการปิดแบบส่งผ่านในลักษณะเดียวกับตรรกะลำดับแรก ส่งผลให้ได้ SO[TC] ตัวดำเนินการ TC สามารถรับตัวแปรลำดับที่สองเป็นอาร์กิวเมนต์ได้ SO[TC] เป็นตัวกำหนดลักษณะของPSPACEเนื่องจากลำดับสามารถอ้างอิงได้ในตรรกะลำดับที่สอง การกำหนดลักษณะนี้จึงไม่ได้ตั้งสมมติฐานเกี่ยวกับโครงสร้างที่มีลำดับ^{[ 20 ]}

คลาส ความซับซ้อน ของเวลาELEMENTARYของฟังก์ชันพื้นฐานสามารถกำหนดลักษณะโดยHOซึ่งเป็นคลาสความซับซ้อนของโครงสร้างที่สามารถรับรู้ได้ด้วยสูตรของตรรกะลำดับสูงตรรกะลำดับสูงเป็นส่วนขยายของตรรกะลำดับแรกและตรรกะลำดับที่สองด้วยตัวบ่งปริมาณลำดับสูง มีความสัมพันธ์ระหว่างลำดับที่ th และอัลกอริทึมที่ไม่กำหนด ซึ่งเวลาถูกจำกัดด้วยระดับของเลขชี้กำลัง^{[ 8 ]}${\displaystyle i}$${\displaystyle i-1}$

เรากำหนดตัวแปรลำดับสูง ตัวแปรลำดับสูงมีอาร์กิวเมนต์ n และแทนเซตของทูเปิลขององค์ประกอบลำดับn ใดๆ โดยปกติจะเขียนด้วยตัวพิมพ์ใหญ่และใช้จำนวนธรรมชาติเป็นเลขชี้กำลังเพื่อระบุลำดับ ตรรกะลำดับสูงคือเซตของสูตรลำดับที่หนึ่งที่เราเพิ่มการกำหนดปริมาณเหนือตัวแปรลำดับสูง ดังนั้นเราจะใช้คำศัพท์ที่กำหนดไว้ใน บทความ FOโดยไม่ต้องกำหนดความหมายอีกครั้ง ${\displaystyle i>1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle i-1}$

HO คือเซตของสูตรที่มีตัวแปรอันดับไม่เกินHO เป็นเซตย่อยของสูตรในรูปแบบโดยที่เป็นตัวบ่งปริมาณ และหมายความว่าเป็นทูเปิลของตัวแปรอันดับ ที่มีตัวบ่งปริมาณเดียวกัน ดังนั้น HO คือเซตของสูตรที่มีการสลับตัวบ่งปริมาณอันดับโดยเริ่มต้นด้วยตามด้วยสูตรอันดับ ${\displaystyle ^{i}}$${\displaystyle i}$${\displaystyle _{j}^{i}}$${\displaystyle \phi =\exists {\overline {X_{1}^{i}}}\forall {\overline {X_{2}^{i}}}\dots Q{\overline {X_{j}^{i}}}\psi }$${\displaystyle Q}$${\displaystyle Q{\overline {X^{i}}}}$${\displaystyle {\overline {X^{i}}}}$${\displaystyle i}$${\displaystyle _{j}^{i}}$${\displaystyle j}$${\displaystyle i}$${\displaystyle \exists }$${\displaystyle i-1}$

โดยใช้สัญลักษณ์มาตรฐานของเททราชันและ. โดยมีเวลา${\displaystyle \exp _{2}^{0}(x)=x}$${\displaystyle \exp _{2}^{i+1}(x)=2^{\exp _{2}^{i}(x)}}$${\displaystyle \exp _{2}^{i+1}(x)=2^{2^{2^{2^{\dots ^{2^{x}}}}}}}$${\displaystyle i}$${\displaystyle 2}$

ทุกสูตรที่มีอันดับth จะเทียบเท่ากับสูตรในรูปแบบปกติ prenex โดยที่เราเขียนปริมาณเหนือตัวแปรที่มีอันดับth ก่อน แล้วจึงเขียนสูตรที่มีอันดับในรูปแบบปกติ ${\displaystyle i}$${\displaystyle i}$${\displaystyle i-1}$

HO เท่ากับคลาสELEMENTARYของฟังก์ชันพื้นฐาน กล่าวให้แม่นยำยิ่งขึ้นคือ หมายถึงลำดับของ เลข 2 ที่ลงท้ายด้วยโดยที่เป็นค่าคงที่ กรณีพิเศษของสิ่งนี้คือซึ่งก็คือทฤษฎีบทของเฟกิน นั่นเอง โดยใช้เครื่องออราเคิลในลำดับชั้นพหุนาม${\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}$${\displaystyle (i-2)}$${\displaystyle n^{c}}$${\displaystyle c}$${\displaystyle \exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Blue}{\mathsf {NP}}}}$${\displaystyle {\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)})^{\Sigma _{j}^{\mathsf {P}}})}$