Log-rank domněnka - Log-rank conjecture

Nevyřešený problém v informatice: Prokázat nebo vyvrátit domněnku log rank. (více nevyřešených problémů v informatice)

v teoretická informatika, domněnka log-rank uvádí, že deterministický složitost komunikace dvoučlenné strany Booleovská funkce je polynomiálně příbuzný logaritmu hodnost její vstupní matice.^[1][2]

Nechat ${ displaystyle D (f)}$ označit deterministická komunikační složitost funkce a necháme ${ displaystyle operatorname {hodnost} (f)}$ označit hodnost její vstupní matice ${ displaystyle M_ {f}}$ (přes realitu). Protože každý protokol používá až ${ displaystyle c}$ bitové oddíly ${ displaystyle M_ {f}}$ maximálně ${ displaystyle 2 ^ {c}}$ jednobarevné obdélníky a každý z nich má hodnocení nejvýše 1,

${ displaystyle D (f) geq log _ {2} operatorname {hodnost} (f).}$

Domněnka log-rank to uvádí ${ displaystyle D (f)}$ je také horní hranice polynomem v log-rank: pro nějakou konstantu ${ displaystyle C}$,

${ displaystyle D (f) = O (( log operatorname {rank} (f)) ^ {C}).}$

Nejznámější horní mez díky Lovettovi^[3]tvrdí, že

${ displaystyle D (f) = O left ({ sqrt { operatorname {rank} (f)}} log operatorname {rank} (f) right).}$

Nejznámější dolní mez kvůli Göösovi, Pitassimu a Watsonovi,^[4] tvrdí, že ${ displaystyle C geq 2}$. Jinými slovy, existuje řada funkcí ${ displaystyle f_ {n}}$, jehož log-rank jde do nekonečna, takhle

${ displaystyle D (f_ {n}) = { tilde { Omega}} (( log operatorname {rank} (f_ {n})) ^ {2}).}$

Nedávno byla vyvrácena přibližná verze domněnky.^[5]

Reference