Bir maksimal antikainin doğrulanması
Sıra teorisinde, bir antikain (Sperner ailesi / dağınıklığı), iki öğenin birbiriyle karşılaştırılamayacağı özelliğine sahip, kısmen sıralı bir kümenin bir alt kümesidir. Bir maksimal antikain, başka bir antikain içinde uygun şekilde bulunmayan antikaindir. Güç setini alalım$\{1,2,\ldots, n\}$Kısmen sıralı setimiz olarak, burada sipariş dahil edilerek verilmektedir. O halde sorum şu, bu kısmen dizilmiş kümenin herhangi bir antikain için, herhangi bir polinom-zaman algoritması var mı ($n$) bu antikainin gerçekten "maksimal" olduğunu doğrulamak için? Başka bir deyişle, herhangi bir alt kümesinin$\{1,2,\ldots, n\}$ya antikainin içinde yer alır ya da antikainin bir kısmını içerir. Burada böyle bir algoritma HERHANGİ antikain için polinom çalışma zamanına sahip olmalıdır .
Güncelleme : Açıklığa kavuşturmak için, burada antikainimizin boyutunu doğrulama algoritmasının parametresi olarak ele alacağım. Başka bir deyişle, sorum şu: çalışma zamanı polinom olan bir doğrulama algoritması var mı?$n$ ve $m$, nerede $m$antikainin boyutudur. Antikainimizin boyutu$m$ üsteldir $n$o zaman böyle bir algoritma önemsizdir (sadece bu öğeleri tek tek karşılaştırmak); ancak verilen antikain O (poli (n)) boyutuna sahipse, bu benim ilgilendiğim durumdur. Örneğin, antikain tarafından verildiğinde$\{\{1\}, \ldots, \{n\}\}$kesinlikle kaba kuvvet karşılaştırması yapmak zorunda değiliz.
Yanıtlar
Açıklama. Başlangıçta bunun tam bir çözüm olduğunu iddia ettim, ancak Emil'in yorumlarda gösterdiği gibi bu yanlıştı. Bununla birlikte, bu argüman, aşağıdaki daha zayıf versiyonu kanıtlamaktadır.
Bir girdi ailesi için karar vermenin birlikte NP-tamamlandığını kanıtlayabilirim $A$ bir set olup olmadığı $S$ bu, içindeki tüm setlerle alakasız $A$. Bu tür ailelere maksimal diyeceğim. Bu, herhangi bir olası polinom zaman algoritmasının, girdi ailesinin, zaten doğrusal boyutlu girdiler için bir antikain olduğundan faydalanması gerektiğini gösterir. Benim indirgem SAT'dan.
Bir CNF verildiğinde $\Psi$ açık $n$ değişkenler, onu bir aileye dönüştürüyoruz $A$ bitmiş $2n$ elemanlar, öyle ki $A$ maksimaldir ancak ve ancak $\Psi$tatmin edilemez olarak. $2n$ elemanlar çiftler halinde gelecek ve bunu şu şekilde ifade ediyorum $i$ ve $i'$.
Her çiftin tamamlayıcısı,$A$ gözetilmeksizin $\Psi$, yani $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Dahası, her cümle için bir küme ekliyoruz$A$ öyle ki eğer $x_i$ cümlecikte, set içerir $i$eğer $\bar x_i$ cümlecikte, set içerir $i'$. Örneğin, fıkra$(x_i\vee \bar x_j)$ seti ekler $ij'$ -e $A$.
Varsayalım $\Psi$tatmin edici. Sonra tatmin edici bir değerlendirme için$x$, seti tanımla $S$ öyle ki $i\in S$ Eğer $x_i$ yanlış ve $i'\in S$ Eğer $x_i$doğru. Bunu kontrol etmek basittir$S$ herhangi bir unsuru ile ilişkili değil $A$.
Farz et ki $A$maksimal değil. Bir set al$S$ herhangi bir unsuru ile ilişkili değil $A$. Tanımlamak$x_i$ eğer doğruysa $i\notin S$ ve eğer yanlış $i'\notin S$aksi takdirde keyfi olarak. Bu tanım gerçekten doğrudur, çünkü$\overline{ii'}\in A$ ima ediyor ki $i,i'\in S$imkansız. Bunu kontrol etmek basittir$x$ tatmin edici bir değerlendirmedir $\Psi$.