Konstrukcje lepsze niż losowe.

10

Interesują mnie przykłady konstrukcji teorii złożoności, które są lepsze niż konstrukcje losowe.

Jedyny znany mi przykład takiej konstrukcji dotyczy kodów korygujących błędy. Kody geometrii algebraicznej są lepsze w niektórych zakresach parametrów niż kody losowe.

Można łatwo skonstruować takie sztuczne przykłady. Interesują mnie przykłady takie jak algebraiczne kody geometrii, w których łatwo jest stworzyć losową konstrukcję i nie jest oczywiste, jak zrobić to lepiej.

— Klim
źródło

7

To pytanie jest strasznie niejasne. Proszę przynajmniej podać, o jakim polu mówisz.

— Dave Clarke

Dodałem tag [big-list] i oflagowałem go dla uwagi moderatora, prosząc go o uczynienie tego pytania wiki społeczności.

— Tsuyoshi Ito,

4

Podoba mi się pytanie, ale możemy chcieć jakoś ograniczyć zakres. Oczywiste jest, że rzeczy takie jak grupy skończone, płaszczyzny rzutowania itp., Jeśli odpowiednio je sparametryzujesz (na przykład liczba trojaków naruszających asocjatywność), będą miały znacznie lepsze parametry niż konstrukcje losowe.

— Peter Shor,

Zgadzam się, że pytanie jest niejasne. Nie wiem, jak ograniczyć zakres. Wszelkie sugestie są mile widziane. Interesuję się interesującymi przykładami. Na przykład, gdy przez długi czas najlepsza była przypadkowa konstrukcja i potrzeba nietrywialnych pomysłów, aby ją pokonać.

— Klim

@Dave, nie jestem pewien, czy to musi być tag CW lub [duża lista], jeśli pytanie jest niejasne, powinniśmy poprosić PO o wyjaśnienie, zauważ, że CW jest nieodwracalne. IMHO, takie pytanie można zmodyfikować w taki sposób, że musi to być pytanie z dużej listy.

— Kaveh

11

Wykresy Ramanujana mają drugą wartość własną (zstopniem wykresu), podczas gdy losowe wykresy osiągają tylko $\lambda_2\leq \frac{2\sqrt{D-1}}{D}$ $D$ whp W zasadzie mamy $\lambda_2\leq \frac{2\sqrt{D-1}}{D} + o(1)$ , przy czym składnikma wartośćautrzymywane na stałym poziomie (jako liczba wierzchołków), więc w pewnym sensie są one optymalne. $\lambda_2\geq \frac{2\sqrt{D-1}}{D} - o(1)$ $o(1)$ $0$ $D$ $N\rightarrow \infty$

— alpoge
źródło

10

$\{ 1,\ldots,N \}$ $\{ 1,\ldots,N\}$ $N^{0.9}$ $N^{1-o(1)}$

— Luca Trevisan
źródło

6

$n$ $n-1$

— Peter Shor
źródło

5

Ogólnie rzecz biorąc, losowe konstrukcje i chciwe konstrukcje osiągają te same granice (np. Kody korekcji błędów). Kiedyś usłyszałem przemówienie Lovasz'a, w którym powiedział, że chciwe wybory i losowe wybory są zasadniczo takie same. Tak więc każda konstrukcja, która pokonałaby tę chciwą konstrukcję, powinna dać odpowiedź na twoje pytanie. Jako szybki przykład tego rodzaju konstrukcje, które osiągają pojemność Spernera grafów, są tego rodzaju. Jak powiedział Peter Shor, istnieje naprawdę wiele przykładów ekstremalnej kombinatoryki.

— Ugo
źródło