การตรวจสอบแอนติเชนสูงสุด
ตามทฤษฎีแล้วแอนติเชน (Sperner family / clutter) เป็นเซตย่อยของเซตที่เรียงลำดับบางส่วนโดยมีคุณสมบัติที่ไม่มีสององค์ประกอบใดเทียบเคียงกันได้ แอนติเชนสูงสุดคือแอนติเชนซึ่งไม่มีอยู่ในแอนติเชนอื่นอย่างเหมาะสม ลองมาดูชุดกำลังของ$\{1,2,\ldots, n\}$ในฐานะชุดที่สั่งซื้อบางส่วนของเราที่นี่คำสั่งซื้อจะได้รับจากการรวม จากนั้นคำถามของฉันคือสำหรับแอนติเชนที่กำหนดของเซตที่ถูกกำหนดบางส่วนนี้มีอัลกอริธึมเวลาพหุนามใด ๆ (เกี่ยวกับ$n$) เพื่อตรวจสอบว่าแอนติเชนนี้ "สูงสุด" จริงหรือ? กล่าวอีกนัยหนึ่งคือการตรวจสอบว่าชุดย่อยของ$\{1,2,\ldots, n\}$มีอยู่ในหรือมีชุดบางอย่างจากแอนติเชน ที่นี่อัลกอริทึมดังกล่าวควรมีเวลาทำงานแบบพหุนามสำหรับแอนติเชนใด ๆ
อัปเดต : เพื่อชี้แจงที่นี่ฉันจะถือว่าขนาดของแอนติเชนของเราเป็นพารามิเตอร์สำหรับอัลกอริทึมการตรวจสอบ กล่าวอีกนัยหนึ่งคำถามของฉันคือ: มีอัลกอริธึมการตรวจสอบหรือไม่ซึ่งรันไทม์เป็นพหุนามใน$n$ และ $m$, ที่ไหน $m$คือขนาดของแอนติเชน เมื่อขนาดของแอนตี้เชนของเรา$m$ เป็นเลขชี้กำลังใน $n$อัลกอริทึมดังกล่าวเป็นเรื่องเล็กน้อย (เพียงแค่เปรียบเทียบองค์ประกอบเหล่านั้นทีละรายการ) แต่เมื่อแอนติเชนที่กำหนดมีขนาด O (poly (n)) นี่เป็นกรณีที่ฉันสนใจ ตัวอย่างเช่นเมื่อได้รับแอนติเชนโดย$\{\{1\}, \ldots, \{n\}\}$เราไม่ต้องทำการเปรียบเทียบกำลังเดรัจฉานอย่างแน่นอน
คำตอบ
ข้อสังเกต. เดิมทีฉันอ้างว่านี่เป็นวิธีแก้ปัญหาเต็มรูปแบบ แต่นั่นเป็นเท็จดังที่แสดงโดย Emil ในความคิดเห็น อย่างไรก็ตามข้อโต้แย้งนี้พิสูจน์ให้เห็นถึงเวอร์ชันที่อ่อนแอกว่าต่อไปนี้
ฉันสามารถพิสูจน์ได้ว่าการตัดสินใจเลือกตระกูลอินพุตนั้นเป็นแบบ co-NP-complete $A$ ไม่ว่าจะมีชุด $S$ ที่ไม่เกี่ยวข้องกับชุดทั้งหมดใน $A$. ฉันจะเรียกครอบครัวแบบนี้ว่าสูงสุด สิ่งนี้แสดงให้เห็นว่าอัลกอริธึมเวลาพหุนามที่เป็นไปได้ใด ๆ ที่เป็นไปได้ต้องใช้ประโยชน์ว่าตระกูลอินพุตเป็นแอนติเชนสำหรับอินพุตขนาดเชิงเส้น การลดของฉันมาจาก SAT
ได้รับ CNF $\Psi$ บน $n$ ตัวแปรเราแปลงเป็นครอบครัว $A$ เกิน $2n$ องค์ประกอบเช่นนั้น $A$ เป็นค่าสูงสุดถ้าและต่อเมื่อ $\Psi$ไม่น่าพอใจ $2n$ องค์ประกอบจะมาเป็นคู่ซึ่งฉันแสดงโดย $i$ และ $i'$.
ส่วนเติมเต็มของทุกคู่มีอยู่ใน$A$ ไม่ว่า $\Psi$ดังนั้น $\overline{11'}\in A$, $\overline{22'}\in A$, ... , $\overline{nn'}\in A$.
ยิ่งไปกว่านั้นสำหรับทุกประโยคเราเพิ่มชุดให้$A$ เช่นนั้นถ้า $x_i$ อยู่ในประโยคชุดประกอบด้วย $i$ในขณะที่ถ้า $\bar x_i$ อยู่ในประโยคชุดประกอบด้วย $i'$. ตัวอย่างเช่นประโยค$(x_i\vee \bar x_j)$ เพิ่มชุด $ij'$ ถึง $A$.
สมมติ $\Psi$เป็นที่น่าพอใจ จากนั้นเพื่อการประเมินที่น่าพอใจ$x$กำหนดชุด $S$ ดังนั้น $i\in S$ ถ้า $x_i$ เป็นเท็จและ $i'\in S$ ถ้า $x_i$เป็นความจริง. ตรงไปตรงมาเพื่อตรวจสอบว่า$S$ ไม่เกี่ยวข้องกับองค์ประกอบใด ๆ ของ $A$.
สมมติว่า $A$ไม่สูงสุด ถ่ายชุด$S$ ไม่เกี่ยวข้องกับองค์ประกอบใด ๆ ของ $A$. กำหนด$x_i$ จะเป็นจริงถ้า $i\notin S$ และเท็จถ้า $i'\notin S$มิฉะนั้นโดยพลการ คำจำกัดความนี้ถูกต้องตามที่$\overline{ii'}\in A$ บอกเป็นนัยว่า $i,i'\in S$เป็นไปไม่ได้ ตรงไปตรงมาเพื่อตรวจสอบว่า$x$ เป็นการประเมินที่น่าพอใจของ $\Psi$.