Verifikasi antikain maksimal
Dalam teori urutan, antichain (Sperner family / clutter) adalah himpunan bagian dari himpunan yang tersusun sebagian, dengan properti bahwa tidak ada dua elemen yang dapat dibandingkan satu sama lain. Antichain maksimal adalah antichain yang tidak terkandung dengan benar di antichain lain. Mari kita ambil set daya$\{1,2,\ldots, n\}$sebagai himpunan yang dipesan sebagian, di sini urutan diberikan melalui penyertaan. Lalu pertanyaan saya adalah, untuk antichain tertentu dari set yang sebagian orded ini, apakah ada algoritma waktu polinomial (sehubungan dengan$n$) untuk memverifikasi bahwa antikain ini memang "maksimal"? Dengan kata lain, memverifikasi subset dari$\{1,2,\ldots, n\}$baik terkandung di, atau berisi beberapa set dari antikain tersebut. Di sini algoritme tersebut harus memiliki waktu proses polinomial untuk antikain APA PUN .
Pembaruan : Untuk memperjelas, di sini saya akan memperlakukan ukuran antichain kami sebagai parameter untuk algoritma verifikasi. Dengan kata lain, pertanyaan saya adalah: apakah ada algoritme verifikasi, yang waktu kerjanya polinomialnya$n$ dan $m$, dimana $m$adalah ukuran antikain tersebut. Saat ukuran antikain kita$m$ eksponensial dalam $n$maka algoritme semacam itu sepele (hanya membandingkan elemen-elemen itu satu per satu); tetapi ketika antikain yang diberikan memiliki ukuran O (poli (n)), ini adalah kasus yang saya minati. Misalnya, saat antikain diberikan oleh$\{\{1\}, \ldots, \{n\}\}$, kita tentunya tidak harus melakukan perbandingan brute force.
Jawaban
Ucapan. Awalnya saya mengklaim ini sebagai solusi lengkap, tetapi itu salah, seperti yang ditunjukkan oleh Emil di komentar. Namun, argumen ini membuktikan versi yang lebih lemah berikut ini.
Saya dapat membuktikan bahwa co-NP-complete untuk memutuskan keluarga masukan $A$ apakah ada satu set $S$ yang tidak terkait dengan semua set di $A$. Saya akan menyebut keluarga seperti itu maksimal. Ini menunjukkan bahwa setiap algoritma waktu polinomial yang mungkin harus mengeksploitasi bahwa keluarga masukan adalah antikain, sudah untuk masukan berukuran linier. Pengurangan saya dari SAT.
Diberikan CNF $\Psi$ di $n$ variabel, kami mengubahnya menjadi keluarga $A$ lebih $2n$ elemen, seperti itu $A$ maksimal jika dan hanya jika $\Psi$dalam ketidakpuasan. Itu$2n$ elemen akan datang berpasangan, yang saya tunjukkan dengan $i$ dan $i'$.
Komplemen dari setiap pasangan terkandung di dalamnya$A$ terlepas dari $\Psi$, jadi $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Selain itu, untuk setiap klausa kami menambahkan satu set ke$A$ seperti itu jika $x_i$ ada di dalam klausa, set berisi $i$, sedangkan jika $\bar x_i$ ada di dalam klausa, set berisi $i'$. Misalnya, klausul$(x_i\vee \bar x_j)$ menambahkan set $ij'$ untuk $A$.
Seharusnya $\Psi$memuaskan. Kemudian untuk evaluasi yang memuaskan$x$, tentukan set $S$ seperti yang $i\in S$ jika $x_i$ salah dan $i'\in S$ jika $x_i$adalah benar. Sangat mudah untuk memeriksanya$S$ tidak ada hubungannya dengan elemen apa pun dari $A$.
Seandainya $A$tidak maksimal. Ambil satu set$S$ tidak terkait dengan elemen apa pun dari $A$. Menetapkan$x_i$ menjadi benar jika $i\notin S$ dan false if $i'\notin S$, sebaliknya secara sewenang-wenang. Definisi ini memang benar, seperti$\overline{ii'}\in A$ menyiratkan itu $i,i'\in S$itu tidak mungkin. Sangat mudah untuk memeriksanya$x$ adalah evaluasi yang memuaskan dari $\Psi$.