Tardos Funkcja kontrprzykład do Bluma

W tym wątku próba próby Norbet Bluma jest zwięźle obalona przez odnotowanie, że funkcja Tardos jest przeciwne do Twierdzenia 6. $P \neq NP$

Twierdzenie 6 : Niech będzie dowolną monotoniczną funkcją boolowską. Załóżmy, że istnieje aproksymator CNF-DNF, którego można użyć do udowodnienia dolnej granicy . Następnie można również wykorzystać do udowodnienia tej samej dolnej granicy dla . $f \in \mathcal{B}_n$ $\mathcal{A}$ $C_m(f)$ $\mathcal{A}$ $C_{st}(f)$

Oto mój problem: funkcja Tardos nie jest funkcją logiczną, więc w jaki sposób spełnia hipotezy Twierdzenia 6?

W niniejszym dokumencie , omawiają złożoność funkcji , który nie jest w ogóle monotoniczny funkcję boolowską, ponieważ zwiększenie krawędzie mogą większa, aby false, gdy było to prawdą z mniejszą liczbą na wejściu. Funkcja na ogół nie oblicza na $\varphi(X) \leq f(v)$ $\varphi(X)$ $\varphi(X) \leq f(v)$ $1$ $\varphi(X) \geq f(v)$ $1$ i na . $T_1$ $0$ $T_0$

W rzeczywistości zestawy testowe i są wybierane dokładnie tak, aby obliczanie na i na z monotonicznością oznaczało twoją funkcję w precyzyjnym obliczaniu CLIQUE (definiują granicę i w sieć danych wejściowych), więc te uwagi sugerują, że funkcja Tardos jest taka sama jak CLIQUE, co oczywiście nie jest prawdą. $T_1$ $T_0$ $1$ $T_1$ $0$ $T_0$ $1$ $0$

Jednak tak wielu ludzi - i tacy znający się na rzeczy - twierdzą, że funkcja Tardos zapewnia natychmiastowy kontrprzykład, więc coś musi mi brakować. Czy możesz podać szczegółowe wyjaśnienie lub dowód dla tych z nas, którzy są zainteresowanymi stronami, ale nie do końca na twoim poziomie?

cc.complexity-theory np-hardness complexity-classes

— użytkownik144527
źródło

Dobrym źródłem byłaby książka Jukny, str. 272 (tuż przed Twierdzeniem 9.28). Ze względu na (nie logiczna) Funkcja

, za funkcję logiczną

który jest obcinanie od

ϕ

$\phi$

f_{ϕ}

$f_\phi$

ϕ

$\phi$

Wynik zostanie zastosowany.

f_{ϕ} (G) = {\begin{cases} 1 & if ϕ (G) \geq \sqrt{n} \\ 0 & otherwise \end{cases}

$f_\phi(G) = \begin{cases} 1 & \text{if } \phi(G) \geq \sqrt{n}\\ 0&\text {otherwise}\end{cases}$

— Klemens C.

Tak więc, dla jasności, mówisz mi, że

będzie oceniać na

na klikach wielkości

f_{ϕ} (G)

$f_\phi(G)$

1

$1$

na wykresach

wierzchołków indukowanych przez właściwe

\sqrt{n}

$\sqrt{n}$

0

$0$

n

$n$

zabarwienia?

⌊ \sqrt{n} - 1 ⌋

$\lfloor \sqrt{n}-1 \rfloor$

— user144527,

Oczywiście nie dotyczy to żadnego

. Jednak funkcja Tardos'

jest na podstawie wykresu monotoniczny funkcją

spełniających

. Tak więc progowanie

robi dokładnie to, co mówisz. Zobacz koniec sekcji 9.8 tutaj .

ϕ

$\phi$

f_{ϕ}

$f_{\phi}$

ϕ

$\phi$

ω (G) \leq ϕ (G) \leq χ (G)

$\omega(G)\leq \phi(G)\leq \chi(G)$

f_{ϕ}

$f_{\phi}$

ϕ

$\phi$

— Stasys

Dobrze. A właściwie nie rozumiem, dlaczego ludzie głosują w dół na twoje (uprawnione ze względu na cały ten hałas wokół tego „dowodu”) pytanie? Teraz autor tej tury roszczenia P! = NP: wyjaśnij, dlaczego „dowód” NIE zadziała dla funkcji Tardos. Wskaż stronę X i linię (y) Y w dokumencie. Wskazówka: błąd będzie w górnej granicy liczby błędów wprowadzonych podczas aproksymacji (negacje mogą zniszczyć wiele wcześniej „prawidłowych” terminów). W przeciwnym razie (bez wyjaśnienia) = brak „dowodu”.

— Stasys

@Stasys, twój pierwszy komentarz może być odpowiedzią.

— Kaveh

więc te uwagi sugerują, że funkcja Tardos jest taka sama jak CLIQUE. $f$

Krótka odpowiedź - NIE.

$k$ $(k-1)$ $G$ $\omega(G) < k$ $\chi(G)\geq k$ $f$ monotoniczna klika przypominająca funkcję logiczną wymaga obwodów niemotonicznych o wielobiegunowym rozmiarze. Więc jeden z tych dwóch artykułów musi być błędny. Papier GLS-1981 trwał już> 35 lat ...

$\varphi(G):=\vartheta(\overline{G})$ $\vartheta$ $\varphi(G)$ $\omega(G)\leq \varphi(G)\leq \chi(G)$ $\vartheta(G)$ $\phi(G)$

$\phi(G)$ $n$
$\phi$
$\omega(G)\leq \phi(G)\leq \chi(G)$ $G$

$f$ $f(G)=1$ $\phi(G)\geq k$ $f$ $f$ $k$ $(k-1)$

Zobacz tutaj szczegóły techniczne.

— Stasys
źródło

Papier GLS-1981 jest tutaj za darmo. Ten artykuł z kolei oparty jest na elipsoidzie Khachiyan-1979. Więc (przynajmniej) jeden z tych trzech dokumentów musi być błędny?

— Tobias Müller,

@Tobias: no cóż, jesteśmy prawie pewni, że te dwa> 35 stare artykuły są poprawne (tyle razy powielone na wykładach, ktoś już zauważył błąd). Problem z obecnym „dowodem” polega na tym, że jest on „z założenia”, a nie „z argumentem” (jak w dwóch wymienionych artykułach). Trudno jest wtedy wskazać konkretne miejsce, w którym zawodzi „konstrukcja”. Zwłaszcza, gdy „konstrukcja” jest tak nieprecyzyjna. Dlatego myślę, że teraz obowiązkiem autora, a nie nas, jest wskazywanie tego miejsca (gdzie Tardos nie przechodzi przez swoją budowę).

— Stasys