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

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

การพิสูจน์ว่าปัญหาการแก้ข้อจำกัดบนโดเมนจำกัดมีคำตอบหรือไม่นั้น โดยทั่วไปแล้วเป็นปัญหา NP-complete นี่เป็นผลสืบเนื่องที่ง่ายจากการที่ปัญหา NP-complete อื่นๆ อีกจำนวนมากสามารถแสดงออกมาในรูปของปัญหาการแก้ข้อจำกัดได้ ปัญหาอื่นๆ เหล่านั้นได้แก่ความสามารถในการทำให้เป็นจริงของประพจน์และ ความสามารถในการ ระบายสีสามสี

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

งานวิจัยแนวทางหนึ่งใช้ความสัมพันธ์ระหว่างปัญหาการแก้ข้อจำกัดกับปัญหาการพิสูจน์การมีอยู่ของโฮโมมอร์ฟิซึมระหว่างโครงสร้างเชิงสัมพันธ์ สองแบบ ความสัมพันธ์นี้ถูกนำมาใช้เพื่อเชื่อมโยงปัญหาการแก้ข้อจำกัดกับหัวข้อที่เกี่ยวข้องกับทฤษฎีฐานข้อมูลแบบ ดั้งเดิม

ปัญหาการวิจัยที่พิจารณาคือการมีอยู่ของการแบ่งแยกสองกลุ่มในชุดของข้อจำกัด นี่คือคำถามที่ว่าชุดข้อจำกัดประกอบด้วยข้อจำกัดเวลาพหุนามและข้อจำกัด NP-complete เท่านั้นหรือไม่ สำหรับข้อจำกัดเชิงสัมพันธ์ (ดูด้านล่าง) คำถามนี้ได้รับการตัดสินในเชิงบวกสำหรับโดเมนบูลีนโดยทฤษฎีบทการแบ่งแยกสองกลุ่มของ Schaefer ^{[ 1 ]}และสำหรับโดเมนจำกัดใดๆ โดย Andrei Bulanov ^{[ 2 ]}และ Dmitriy Zhuk ^{[ 3 ]}อย่างอิสระในปี 2017

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

ความสามารถในการจัดการเชิงตรรกสามารถทำได้โดยการจำกัดขอบเขตหรือข้อจำกัดที่เป็นไปได้ โดยเฉพาะอย่างยิ่ง มีการพิจารณาข้อจำกัดสองประเภทดังนี้:

• ข้อจำกัดเชิงสัมพันธ์กำหนดขอบเขตของโดเมนและค่าต่างๆ ที่สอดคล้องกับข้อจำกัดเหล่านั้น
• ข้อจำกัดเชิงโครงสร้างได้กำหนดวิธีการกระจายข้อจำกัดต่างๆ ไปสู่ตัวแปรต่างๆ

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

ภาษาข้อจำกัดจะเรียกว่าสามารถแก้ไขได้ง่าย (tractable language) หากมีอัลกอริธึมพหุนามที่สามารถแก้ปัญหาทั้งหมดโดยใช้ภาษานั้นได้ กล่าวคือ โดยใช้โดเมนและความสัมพันธ์ที่ระบุไว้ในโดเมน ตัวอย่างของภาษาข้อจำกัดที่สามารถแก้ไขได้ง่ายคือ โดเมนแบบไบนารีและข้อจำกัดแบบไบนารี ในทางทฤษฎี ข้อจำกัดนี้สอดคล้องกับการอนุญาตเฉพาะโดเมนที่มีขนาด 2 และเฉพาะข้อจำกัดที่มีความสัมพันธ์แบบไบนารี เท่านั้น แม้ว่าข้อเท็จจริงข้อที่สองจะบ่งชี้ว่าขอบเขตของข้อจำกัดเป็นแบบไบนารี แต่นี่ไม่ใช่ข้อจำกัดเชิงโครงสร้าง เพราะไม่ได้ห้ามไม่ให้วางข้อจำกัดใดๆ บนตัวแปรคู่ใดๆ ก็ตาม อนึ่ง ปัญหาจะกลายเป็น NP-complete หากยกเลิกข้อจำกัดใดข้อจำกัดหนึ่ง: ข้อจำกัดแบบไบนารีและโดเมนแบบไตรนารีสามารถแสดง ปัญหา การระบายสีกราฟ 3 สีได้ในขณะที่ข้อจำกัดแบบไตรนารีและโดเมนแบบไบนารีสามารถแสดง3-SAT ได้ ซึ่งทั้งสองปัญหานี้เป็น NP-complete

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

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

กรณีเฉพาะที่ได้จากการจำกัดขอบเขตให้อยู่ในภาษาข้อจำกัดแบบจำกัด เรียกว่าปัญหาที่ไม่สม่ำเสมอ (non-uniform problem ) ปัญหาเหล่านี้มักถูกพิจารณาเมื่อแสดงความพึงพอใจต่อข้อจำกัดในรูปของปัญหาโฮโมมอร์ฟิซึม (homomorphism problem) ดังที่อธิบายไว้ด้านล่างปัญหาที่สม่ำเสมอ (uniform problems) ก็ถูกกำหนดขึ้นในบริบทของปัญหาโฮโมมอร์ฟิซึมเช่นกัน ปัญหาที่สม่ำเสมอสามารถนิยามได้ว่าเป็นผลรวมของชุดปัญหาที่ไม่สม่ำเสมอ (ซึ่งอาจมีจำนวนอนันต์) ปัญหาที่สม่ำเสมอซึ่งประกอบด้วยชุดปัญหาที่ไม่สม่ำเสมอจำนวนอนันต์ อาจแก้ไขได้ยาก แม้ว่าปัญหาที่ไม่สม่ำเสมอทั้งหมดเหล่านั้นจะแก้ไขได้ก็ตาม

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

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

ปัญหาการแก้ข้อจำกัดสามารถแปลงให้อยู่ในรูปของปัญหาอื่นๆ ได้ ซึ่งจะนำไปสู่เงื่อนไขที่เทียบเท่ากับความสามารถในการจัดการได้ การแปลงที่ใช้กันมากที่สุดคือการแปลงให้อยู่ในรูปของปัญหา โฮโมมอร์ฟิซึม

มีการเชื่อมโยงระหว่างการแก้ปัญหาข้อจำกัดและทฤษฎีฐานข้อมูลในรูปแบบของการสอดคล้องกันระหว่างปัญหาการแก้ปัญหาข้อจำกัดและปัญหาการตรวจสอบว่ามีโฮโมมอร์ฟิซึมระหว่างโครงสร้างเชิงสัมพันธ์สองโครงสร้างหรือไม่ โครงสร้างเชิงสัมพันธ์คือการแสดงทางคณิตศาสตร์ของฐานข้อมูลเชิงสัมพันธ์กล่าวคือ เป็นเซตของค่าและเซตของความสัมพันธ์เหนือค่าเหล่านั้น ในทางคณิตศาสตร์โดยที่แต่ละเป็นความสัมพันธ์เหนือนั่นคือ เซตของทูเปิลของค่าของ ${\displaystyle A=(V,R_{1}^{A},\ldots ,R_{n}^{A})}$${\displaystyle R_{i}^{A}}$${\displaystyle V}$${\displaystyle V}$

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

อย่างไรก็ตาม ปัญหาการแก้ข้อจำกัดนั้นเกี่ยวข้องกับปัญหาการพิสูจน์การมีอยู่ของโฮโมมอร์ฟิซึมระหว่างโครงสร้างเชิงสัมพันธ์สองโครงสร้าง โฮโมมอร์ฟิซึมคือฟังก์ชันจากค่าของความสัมพันธ์แรกไปยังค่าของความสัมพันธ์ที่สอง ซึ่งเมื่อนำไปใช้กับค่าทั้งหมดของความสัมพันธ์ในโครงสร้างแรก จะทำให้ค่าเหล่านั้นกลายเป็นเซตย่อยของความสัมพันธ์ที่สอดคล้องกันในโครงสร้างที่สอง กล่าวคือ เป็นโฮโมมอร์ฟิซึมจากไปถ้าเป็นฟังก์ชันจากไปโดยที่ถ้า แล้ว${\displaystyle h}$${\displaystyle A=(V,R_{1}^{A},\ldots ,R_{n}^{A})}$${\displaystyle B=(D,R_{1}^{B},\ldots ,R_{n}^{B})}$${\displaystyle V}$${\displaystyle D}$${\displaystyle (x_{1},\ldots ,x_{k})\in R_{i}^{A}}$${\displaystyle (h(x_{1}),\ldots ,h(x_{k}))\in R_{i}^{B}}$

สามารถสร้างความสัมพันธ์โดยตรงระหว่างปัญหาการแก้ข้อจำกัดและปัญหาโฮโมมอร์ฟิซึมได้ สำหรับปัญหาการแก้ข้อจำกัดที่กำหนด เราสามารถสร้างโครงสร้างเชิงสัมพันธ์สองคู่ โดยคู่แรกเข้ารหัสตัวแปรและลายเซ็นของข้อจำกัด คู่ที่สองเข้ารหัสโดเมนและความสัมพันธ์ของข้อจำกัด ความสามารถในการแก้ข้อจำกัดนั้นสอดคล้องกับการหาค่าสำหรับตัวแปรทุกตัว ซึ่งเมื่อแทนค่าในลายเซ็นแล้ว ค่าดังกล่าวจะกลายเป็นทูเปิลในความสัมพันธ์ของข้อจำกัด ซึ่งเป็นไปได้ก็ต่อเมื่อการประเมินค่านี้เป็นโฮโมมอร์ฟิซึมระหว่างโครงสร้างเชิงสัมพันธ์ทั้งสอง

การจับคู่แบบผกผันคือสิ่งที่ตรงกันข้าม: เมื่อมีโครงสร้างเชิงสัมพันธ์สองโครงสร้าง โครงสร้างหนึ่งจะเข้ารหัสค่าของโครงสร้างแรกในตัวแปรของปัญหาการแก้ข้อจำกัด และอีกโครงสร้างหนึ่งจะเข้ารหัสค่าของโครงสร้างที่สองในโดเมนของปัญหาเดียวกัน สำหรับทุกคู่ของทุกความสัมพันธ์ในโครงสร้างแรก จะมีข้อจำกัดที่มีค่าเป็นความสัมพันธ์ที่สอดคล้องกันของโครงสร้างที่สอง ด้วยวิธีนี้ โฮโมมอร์ฟิซึมจึงสอดคล้องกับการแมปทุกขอบเขตของทุกข้อจำกัด (ทุกคู่ของทุกความสัมพันธ์ในโครงสร้างแรก) ไปยังคู่ในความสัมพันธ์ของข้อจำกัด (คู่ในความสัมพันธ์ที่สอดคล้องกันของโครงสร้างที่สอง)

ปัญหาการแก้ข้อจำกัดที่ไม่สม่ำเสมอ คือ ข้อจำกัดที่โครงสร้างที่สองของปัญหาโฮโมมอร์ฟิซึมถูกกำหนดไว้ตายตัว กล่าวอีกนัยหนึ่ง โครงสร้างเชิงสัมพันธ์ทุกโครงสร้างกำหนดปัญหาที่ไม่สม่ำเสมอ นั่นคือ การบอกว่าโครงสร้างเชิงสัมพันธ์นั้นเป็นโฮโมมอร์ฟิกกับโครงสร้างนั้นหรือไม่ ข้อจำกัดที่คล้ายกันนี้สามารถกำหนดให้กับโครงสร้างแรกได้ สำหรับโครงสร้างแรกที่กำหนดไว้ตายตัว ปัญหาโฮโมมอร์ฟิซึมจะสามารถแก้ไขได้ เพราะจะมีฟังก์ชันจากโครงสร้างแรกไปยังโครงสร้างที่สองเพียงจำนวนพหุนามเท่านั้น ปัญหาการแก้ข้อจำกัดที่สม่ำเสมอ คือ ข้อจำกัดที่กำหนดขึ้นเองสำหรับเซตของโครงสร้างสำหรับโครงสร้างแรกและโครงสร้างที่สองของปัญหาโฮโมมอร์ฟิซึม

เนื่องจากปัญหาโฮโมมอร์ฟิซึมเทียบเท่ากับการประเมินแบบสอบถามเชิงเชื่อมโยงและการบรรจุแบบสอบถามเชิงเชื่อมโยงดังนั้นปัญหาทั้งสองนี้จึงเทียบเท่ากับการแก้ปัญหาข้อจำกัดด้วยเช่นกัน

ข้อจำกัดแต่ละข้อสามารถมองได้ว่าเป็นตารางในฐานข้อมูลโดยที่ตัวแปรถูกตีความว่าเป็นชื่อแอตทริบิวต์ และความสัมพันธ์คือชุดของระเบียนในตาราง คำตอบของปัญหาการแก้ข้อจำกัดคือผลลัพธ์ของการเชื่อมตารางแบบภายใน (inner join ) ที่แสดงถึงข้อจำกัดเหล่านั้น ดังนั้น ปัญหาการมีอยู่ของคำตอบจึงสามารถกำหนดใหม่ได้เป็นปัญหาการตรวจสอบว่าผลลัพธ์ของการเชื่อมตารางแบบภายในของตารางจำนวนหนึ่งไม่ว่างเปล่าหรือไม่

ภาษาข้อจำกัดบางภาษา (หรือปัญหาที่ไม่สม่ำเสมอ) เป็นที่ทราบกันว่าสอดคล้องกับปัญหาที่สามารถแก้ไขได้ในเวลาพหุนามและบางภาษาเป็นที่ทราบกันว่าแสดงถึง ปัญหา NP-completeอย่างไรก็ตาม เป็นไปได้ที่ภาษาข้อจำกัดบางภาษาจะไม่เป็นทั้งสองอย่างทฤษฎีบทของ Ladner เป็นที่ทราบกัน ว่าหาก P ไม่เท่ากับ NP จะมีปัญหาใน NP ที่ไม่ใช่ทั้งปัญหาเวลาพหุนามและปัญหา NP-hard สำหรับปัญหาข้อจำกัดที่มีภาษาข้อจำกัดที่กำหนดไว้และไม่มีข้อจำกัดเชิงโครงสร้าง ปัญหาระดับกลางดังกล่าวไม่มีอยู่จริง ดังที่ Andrei Bulatov ^{[ 2 ]}และ Dmitriy Zhuk ^{[ 3 ]} ได้พิสูจน์ อย่างอิสระในปี 2017 หากไม่มีภาษา Ladner ใดที่สามารถแสดงเป็นปัญหาความพึงพอใจข้อจำกัดได้ เซตของภาษาข้อจำกัดทั้งหมดสามารถแบ่งได้อย่างแม่นยำออกเป็นภาษาที่กำหนดปัญหาเวลาพหุนามและภาษาที่กำหนดปัญหา NP-complete นั่นคือ เซตนี้แสดงให้เห็นถึงการ แบ่งแยก

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

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

ผลลัพธ์เชิงความซับซ้อนบางอย่างพิสูจน์ได้ว่าข้อจำกัดบางอย่างเป็นพหุนาม โดยไม่ได้พิสูจน์ว่าข้อจำกัดอื่นๆ ที่เป็นไปได้ทั้งหมดในลักษณะเดียวกันนั้นเป็นปัญหา NP-hard

เงื่อนไขที่เพียงพอสำหรับความสามารถในการประมวลผลนั้นเกี่ยวข้องกับความสามารถในการแสดงออกในDatalog คำสั่งค้นหา แบบบูลีนใน Datalog จะให้ค่าความจริงแก่เซตของค่าคงที่บนตัวอักษรที่กำหนด โดยแต่ละค่าคงที่เป็นนิพจน์ในรูปแบบ; ด้วยเหตุนี้ คำสั่งค้นหาแบบบูลีนใน Datalog จึงแสดงถึงเซตของเซตของค่าคงที่ เนื่องจากสามารถพิจารณาได้ว่ามีความหมายเทียบเท่ากับเซตของเซตของค่าคงที่ทั้งหมดที่ประเมินค่าได้เป็นจริง ${\displaystyle L(a_{1},\ldots ,a_{n})}$

ในทางกลับกัน ปัญหาที่ไม่สม่ำเสมอสามารถมองได้ว่าเป็นวิธีหนึ่งในการแสดงชุดที่คล้ายกัน สำหรับปัญหาที่ไม่สม่ำเสมอที่กำหนด ชุดของความสัมพันธ์ที่สามารถใช้ในข้อจำกัดนั้นคงที่ ดังนั้นจึงสามารถตั้งชื่อที่ไม่ซ้ำกันให้กับความสัมพันธ์เหล่านั้นได้ ตัวอย่างของปัญหาที่ไม่สม่ำเสมอนี้สามารถเขียนได้เป็นชุดของตัวแปรในรูปแบบในบรรดาตัวอย่าง/ชุดของตัวแปรเหล่านี้ บางส่วนสามารถหาคำตอบได้และบางส่วนไม่สามารถหาคำตอบได้ ว่าชุดของตัวแปรนั้นสามารถหาคำตอบได้หรือไม่ขึ้นอยู่กับความสัมพันธ์ ซึ่งระบุไว้ในปัญหาที่ไม่สม่ำเสมอ ในทางกลับกัน ปัญหาที่ไม่สม่ำเสมอจะบอกว่าชุดของตัวแปรใดแสดงถึงตัวอย่างที่สามารถหาคำตอบได้ และชุดใดแสดงถึงตัวอย่างที่ไม่สามารถหาคำตอบได้ เมื่อตั้งชื่อความสัมพันธ์แล้ว ปัญหาที่ไม่สม่ำเสมอจะแสดงชุดของชุดของตัวแปร: ตัวแปรที่เกี่ยวข้องกับตัวอย่างที่สามารถหาคำตอบได้ (หรือตัวอย่างที่ไม่สามารถหาคำตอบได้) ${\displaystyle R_{1},\ldots ,R_{n}}$${\displaystyle R_{i}(x_{1},\ldots ,x_{n})}$

เงื่อนไขที่เพียงพอสำหรับการแก้ปัญหาได้คือ ปัญหาที่ไม่สม่ำเสมอจะสามารถแก้ไขได้หากเซตของตัวอย่างที่ไม่สามารถหาคำตอบได้สามารถแสดงได้ด้วยคำสั่งค้นหาข้อมูลแบบบูลีน (Boolean Datalog query) กล่าวอีกนัยหนึ่ง หากเซตของเซตของค่าคงที่ที่แสดงถึงตัวอย่างที่ไม่สามารถหาคำตอบได้ของปัญหาที่ไม่สม่ำเสมอ คือเซตของเซตของค่าคงที่ที่ตรงกับคำสั่งค้นหาข้อมูลแบบบูลีน ปัญหาที่ไม่สม่ำเสมอนั้นก็จะสามารถแก้ไขได้

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

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

1. บังคับใช้ความสอดคล้องของส่วนโค้ง หากกราฟหลักไม่มีวงจร
2. การบังคับใช้ความสอดคล้องของส่วนโค้งทิศทางสำหรับการเรียงลำดับของตัวแปรที่ทำให้กราฟลำดับของข้อจำกัดมีความกว้าง 1 (การเรียงลำดับดังกล่าวมีอยู่ก็ต่อเมื่อกราฟดั้งเดิมเป็นต้นไม้ แต่ไม่ใช่ทุกการเรียงลำดับของต้นไม้ที่จะสร้างความกว้าง 1)
3. บังคับใช้ความสอดคล้องของเส้นทางทิศทางที่แข็งแกร่งสำหรับการเรียงลำดับของตัวแปรที่ทำให้กราฟหลักมีความกว้างที่เหนี่ยวนำเท่ากับ 2

เงื่อนไขที่ต่อยอดจากเงื่อนไขสุดท้ายนี้ใช้ได้กับปัญหาการแก้ข้อจำกัดที่ไม่ใช่แบบไบนารี กล่าวคือ สำหรับปัญหาทั้งหมดที่มีลำดับที่ทำให้กราฟหลักมีความกว้างที่เหนี่ยวนำซึ่งถูกจำกัดด้วยค่าคงที่ i การบังคับใช้ความสอดคล้อง i-ทิศทางที่เข้มงวดสามารถทำได้และช่วยให้สามารถสร้างความพึงพอใจได้

ปัญหาการแก้ข้อจำกัดที่ประกอบด้วยข้อจำกัดแบบไบนารีเท่านั้น สามารถมองได้ว่าเป็นกราฟโดยที่จุดยอดคือตัวแปร และขอบแสดงถึงการมีอยู่ของข้อจำกัดระหว่างตัวแปรสองตัว กราฟนี้เรียกว่ากราฟไกฟ์แมนหรือกราฟข้อจำกัดดั้งเดิม (หรือเรียกสั้น ๆ ว่ากราฟดั้งเดิม) ของปัญหา

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

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

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

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

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

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

เครื่องมืออเนกประสงค์นี้มีพื้นฐานมาจากการสังเกตว่า ความสัมพันธ์ทุกอย่างที่ประกอบด้วยทูเพิลสามารถกำหนดได้โดยการฉายภาพความสัมพันธ์ที่ประกอบด้วยคอลัมน์ที่เป็นไปได้ทั้งหมดขององค์ประกอบจากโดเมน ตัวอย่างเช่น ตารางต่อไปนี้แสดงการฉายภาพดังกล่าว: ${\displaystyle k}$${\displaystyle k}$

abcdefghbd --------------- --- 1 1 1 1 0 0 0 0 -> 1 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 

ถ้าตารางทางซ้ายเป็นเซตของคำตอบของปัญหาการแก้ข้อจำกัด ตัวแปร x และy จะถูกจำกัดให้มีค่าตามตารางทางขวา ดังนั้น ปัญหาการแก้ข้อจำกัดจึงสามารถนำมาใช้กำหนดข้อจำกัดที่มีความสัมพันธ์กับตารางทางขวา ซึ่งอาจไม่ได้อยู่ในภาษาของข้อจำกัดก็ได้ ${\displaystyle b}$${\displaystyle d}$

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

ยกตัวอย่างเช่น หากภาษาประกอบด้วยความสัมพันธ์แบบไบนารีที่แสดงถึงการแยกแบบบูลีน (ความสัมพันธ์ที่ประกอบด้วยทูเปิลสองตัวทั้งหมดที่มีอย่างน้อยหนึ่งค่าเป็น 1) ความสัมพันธ์นี้จะถูกวางเป็นข้อจำกัดบนและเนื่องจากค่าของพวกมันในตารางด้านบนคือและอีกครั้งเนื่องจากค่าทั้งหมดนี้เป็นไปตามข้อจำกัด ข้อจำกัดจึงถูกวาง ในทางกลับกัน ข้อจำกัดที่มีความสัมพันธ์นี้จะไม่ถูกวางบนและเนื่องจากข้อจำกัดของตารางด้านบนสำหรับตัวแปรสองตัวนี้มีเป็นแถวที่สาม และการประเมินนี้ละเมิดข้อจำกัดนั้น ${\displaystyle a}$${\displaystyle b}$${\displaystyle (1,1)}$${\displaystyle (1,1)}$${\displaystyle (1,0)}$${\displaystyle b}$${\displaystyle d}$${\displaystyle (0,0)}$

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

เมื่อกำหนดความสัมพันธ์เฉพาะแล้ว เราสามารถตรวจสอบความสามารถในการแสดงความสัมพันธ์นั้นในภาษาได้โดยพิจารณาจากรายการตัวแปรใดๆ ที่คอลัมน์ในตารางด้านบน (คำตอบ "ในอุดมคติ" ของอุปกรณ์สากล) ก่อให้เกิดความสัมพันธ์นั้น ความสัมพันธ์นั้นสามารถแสดงในภาษาได้ก็ต่อเมื่อคำตอบของอุปกรณ์สากลตรงกับความสัมพันธ์เมื่อฉายภาพลงบนรายการตัวแปรดังกล่าว กล่าวอีกนัยหนึ่ง เราสามารถตรวจสอบความสามารถในการแสดงได้โดยการเลือกตัวแปร "เสมือนว่า" คำตอบของอุปกรณ์สากลเป็นดังในตาราง แล้วตรวจสอบว่าข้อจำกัดของคำตอบ "จริง" นั้นเหมือนกับความสัมพันธ์หรือไม่ ในตัวอย่างข้างต้น เราสามารถตรวจสอบความสามารถในการแสดงความสัมพันธ์ในตารางทางด้านขวาได้โดยการดูว่าคำตอบของอุปกรณ์สากล เมื่อจำกัดไว้ที่ตัวแปรและนั้นตรงกับแถวของตารางนี้หรือ ไม่${\displaystyle b}$${\displaystyle d}$

เงื่อนไขที่จำเป็นสำหรับความสามารถในการจัดการสามารถแสดงได้ในรูปของอุปกรณ์อเนกประสงค์ วิธีแก้ปัญหาของอุปกรณ์ดังกล่าวสามารถแสดงเป็นตารางได้ดังนี้:

abcdefgh --------------- 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 (คำตอบที่มีอยู่ตามคำนิยาม) 1 0 1 0 1 0 1 0 --------------- .... 1 0 0 1 1 1 0 0 (อาจมีวิธีแก้ปัญหาอื่นๆ อีก) .... 

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

ฟังก์ชันที่สอดคล้องกับคำตอบสามารถคำนวณได้จากส่วนแรกของตารางด้านบนและคำตอบนั้น ตัวอย่างเช่น สำหรับคำตอบสุดท้ายที่ทำเครื่องหมายไว้ในตาราง ฟังก์ชันนี้สามารถกำหนดได้โดยใช้ค่าต่อไปนี้: ประการแรก ค่าทั้งสามนี้คือส่วนแรกของแถว "c" ในตาราง ประการที่สอง ค่าของฟังก์ชันคือค่าของคำตอบในคอลัมน์เดียวกัน นั่นคือ 0 ${\displaystyle 1,0,1}$

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

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

ในทางทฤษฎีแล้ว ฟังก์ชันการบีบอัด (squashing function) คือฟังก์ชันที่กำหนดว่าสำหรับทุกค่าในพาร์ติชันเดียวกัน และสำหรับทุกคู่ลำดับ (tuple) ฟังก์ชันนี้จะเป็นจริง ${\displaystyle D_{1},\ldots ,D_{n}}$${\displaystyle D}$${\displaystyle s:D\rightarrow D}$${\displaystyle s(x)=s(y)}$${\displaystyle x,y}$${\displaystyle \langle x_{1},\ldots ,x_{n}\rangle \in R}$${\displaystyle \langle s(x_{1}),\ldots ,s(x_{n})\rangle \in R}$

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

ภาษาที่มีข้อจำกัดซึ่งไม่มีฟังก์ชันการบีบอัดเรียกว่าภาษาลดรูป หรือกล่าวอีกนัยหนึ่งคือ ภาษาที่ได้นำการลดรูปทั้งหมดผ่านฟังก์ชันการบีบอัดมาใช้แล้ว

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