ในทฤษฎีความซับซ้อนของการคำนวณ CC (Comparator Circuits)คือกลุ่มความซับซ้อนที่ประกอบด้วยปัญหาการตัดสินใจซึ่งสามารถแก้ไขได้ด้วยวงจร เปรียบเทียบ ที่มีขนาดเป็นพหุนาม

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

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

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

ปัญหาค่าวงจรเปรียบเทียบ (CCVP) คือปัญหาของการประเมินค่าวงจรเปรียบเทียบโดยกำหนดการเข้ารหัสของวงจรและอินพุตของวงจร คลาสความซับซ้อนCCถูกกำหนดให้เป็นคลาสของปัญหาlogspaceที่ลดรูปเป็น CCVP ได้^{[ 1 ]}คำจำกัดความที่เทียบเท่ากัน^{[ 2 ]}คือคลาสของปัญหาAC ⁰ที่ลดรูปเป็น CCVP ได้

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

ถ้ากำหนดให้สายกลางเป็นเอาต์พุต และสายต่างๆ ถูกกำหนดด้วยตัวแปรอินพุต 16 ตัวที่แตกต่างกัน วงจรเปรียบเทียบที่ได้จะคำนวณค่าส่วนใหญ่ เนื่องจากมีเครือข่ายเรียงลำดับที่สามารถสร้างได้ในAC 0 ^{ดังนั้น}จึงแสดงให้เห็นว่าฟังก์ชันส่วนใหญ่อยู่ในCC

ปัญหาในCCจะเรียกว่าCC -complete ถ้าทุกปัญหาในCCสามารถลดรูปมาเป็นปัญหานั้นได้โดยใช้ การลด รูปเชิงลอการิทึมปัญหาค่าวงจรเปรียบเทียบ (CCVP) เป็นปัญหาCC -complete

ในปัญหาการแต่งงานที่มั่นคงจะมีจำนวนชายและหญิงเท่ากัน แต่ละคนจะจัดอันดับสมาชิกทั้งหมดของเพศตรงข้าม การจับคู่ระหว่างชายและหญิงจะมั่นคงหากไม่มีชายและหญิงที่ไม่ได้จับคู่กันซึ่งชอบกันมากกว่าคู่ครองปัจจุบันของตน การจับคู่ที่มั่นคงมีอยู่เสมอ ในบรรดาการจับคู่ที่มั่นคง มีการจับคู่หนึ่งที่ผู้หญิงแต่ละคนได้รับผู้ชายที่ดีที่สุดเท่าที่เธอเคยได้รับในการจับคู่ที่มั่นคงใดๆ ซึ่งเรียกว่า การจับคู่ที่มั่นคง ที่เหมาะสมที่สุดสำหรับผู้หญิงเวอร์ชันการตัดสินใจของปัญหาการจับคู่ที่มั่นคงคือ เมื่อกำหนดการจัดอันดับของชายและหญิงทั้งหมดแล้ว ชายและหญิงที่กำหนดจะจับคู่กันในการจับคู่ที่มั่นคงที่เหมาะสมที่สุดสำหรับผู้หญิงหรือไม่ แม้ว่าอัลกอริทึม Gale–Shapley แบบคลาสสิกจะไม่สามารถนำไปใช้เป็นวงจรเปรียบเทียบได้ แต่ Subramanian ^{[ 3 ]}ได้คิดค้นอัลกอริทึมที่แตกต่างออกไปซึ่งแสดงให้เห็นว่าปัญหานี้อยู่ในCCปัญหานี้ยังเป็นCC -complete ด้วย

ปัญหาอีกประการหนึ่งที่CC -complete คือการจับคู่สูงสุดตามลำดับตัวอักษร^{[ 3 ]}ในปัญหานี้ เราได้รับกราฟสองส่วนที่มีลำดับบนจุดยอดและขอบ การจับคู่สูงสุดตามลำดับตัวอักษรจะได้รับโดยการจับคู่จุดยอดจากการแบ่งสองส่วนแรกกับจุดยอดที่น้อยที่สุดที่มีอยู่จากการแบ่งสองส่วนที่สอง ปัญหาถามว่าขอบที่กำหนดเป็นส่วนหนึ่งของการจับคู่นี้หรือไม่

Scott Aaronsonแสดงให้เห็นว่าแบบจำลองก้อนกรวดเป็นCC -complete ^{[ 4 ]}ในปัญหานี้ เราได้รับจำนวนก้อนกรวดเริ่มต้น (เข้ารหัสในรูปแบบเอกภาค ) และคำอธิบายของโปรแกรมซึ่งอาจมีคำสั่งเพียงสองประเภทเท่านั้น: รวมกองสองกองที่มีขนาดต่างกัน${\displaystyle y}$และ${\displaystyle z}$เพื่อให้ได้กองขนาดใหม่${\displaystyle y+z}$หรือแบ่งกองขนาดออกเป็นส่วนๆ${\displaystyle y}$กองเป็นกองขนาดต่างๆ${\displaystyle \lceil y/2\rceil }$และ${\displaystyle \lfloor y/2\rfloor }$ปัญหาคือการตัดสินใจว่ามีก้อนกรวดอยู่ในกองใดกองหนึ่งหรือไม่หลังจากที่โปรแกรมทำงานเสร็จแล้ว เขาใช้สิ่งนี้เพื่อแสดงให้เห็นว่าปัญหาการตัดสินใจว่าลูกบอลใดไปถึงจุดรับลูกบอลที่กำหนดไว้ใน อุปกรณ์ที่คล้ายกับ Digi-Comp II นั้นก็เป็นปัญหาCC -complete เช่นกัน

ปัญหาการประเมินวงจรเปรียบเทียบสามารถแก้ไขได้ในเวลาพหุนาม ดังนั้นCCจึงบรรจุอยู่ในP ("ความเป็นสากลของวงจร") ในทางกลับกัน วงจรเปรียบเทียบสามารถแก้ปัญหาการเข้าถึงแบบมีทิศทางได้^{[ 3 ]}ดังนั้นCCจึงบรรจุNLมีโลกสัมพัทธ์ที่CCและNCไม่สามารถเปรียบเทียบกันได้^{[ 2 ]}ดังนั้นการบรรจุทั้งสองจึงเข้มงวด

• สวนสัตว์แห่งความซับซ้อน : ซีซี