Czy istnieje lepsza niż liniowa dolna granica dla faktoringu i dziennika dyskretnego?

Czy istnieją odniesienia, które zawierają szczegółowe informacje na temat dolnych granic obwodu dla konkretnych trudnych problemów pojawiających się w kryptografii, takich jak faktoring liczb całkowitych, problem logarytmu dyskretnego z liczbami pierwszymi / złożonymi i jego wariant nad grupą punktów krzywych eliptycznych (i ich wielowymiarowych odmian abelowych) i ogólne ukryty problem z podgrupą?

Czy któryś z tych problemów ma dolną granicę złożoności liniowej?

— vs
źródło

Oczywiście wiesz, że nie jest znana dolna granica lepsza niż 5n dla złożoności obwodu, dla <i> dowolnej </i> jawnej funkcji, nie tylko dla tych, o których wspomniałeś. Powinieneś więc podać pytanie. Lepsze granice są znane tylko dla obwodów ograniczonych . Być może możesz znaleźć częściowe odpowiedzi na stronie głównej <a href=" web.science.mq.edu.au/~igor "rel="nofollow"> Igor Sparliński. </a>

— Stasys

Nie jestem do końca pewien, co masz na myśli pod tym „ciekawym faktem”. W każdym razie aktualny stan złożoności obwodów jest podany w mojej nadchodzącej książce thi.informatik.uni-frankfurt.de/~jukna/BFC-book . Użytkownik: przyjaciel Hasło: catchthecat

— Stasys

@Stasys, pamiętam, że uczeń z Rosji mówił o swojej dolnej granicy formy 7n + O (1) w oparciu o eliminację bramki w Praskiej Szkole Jesiennej dwa lata temu, ale nie pamiętam żadnych szczegółów.

— Kaveh

Kaveh, to dolna granica (7/3) nc, a nie 7n. Udowodnili to Arist Kojevnikov i Sasha Kulikov z Petersburga. Zaletą tego dowodu jest jego prostota, a nie numeryczność. Później podali prosty dowód dolnej granicy 3n-o (1) dla obwodów ogólnych (wszystkie bramki Fanin-2 są dozwolone). Jednak dla bardzo skomplikowanych funkcji - afinicznych dyspergatorów. Artykuły są dostępne online pod adresem: logic.pdmi.ras.ru/~kulikov/papers . Właściwie ciasno związane 7n-7 zostały pokazane przez Redkina (1973) dla funkcji parzystości, ale tylko wtedy, gdy dozwolone są tylko bramki NIE i AND. Jeśli dozwolony jest także OR, jego granica wynosi 4n-4 (również ciasno!).

— Stasys,

@StasysJukna: kombinacja twoich komentarzy jest odpowiednia jako odpowiedź.

— Suresh Venkat

@Suresh: zgodnie z twoją radą oto moja „odpowiedź”. Status dolnych granic obwodu jest dość przygnębiający. Oto „aktualne rekordy”:

$4n-4$ $\{\land,\lor,\neg\}$ $7n-7$ $\{\land,\neg\}$ $\{\lor,\neg\}$ $\oplus_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n$
$5n-o(n)$
$3n-o(n)$ $(7/3)n-o(1)$ $3n-o(1)$
$n^{3-o(1)}$ $\{\land,\lor,\neg\}$
$\Omega(n^2/\log n)$ $2$ $\Omega(n^2/\log^2 n)$ $\Omega(n^{3/2}/\log n)$

Więc twoje pytanie: „Czy któryś z tych problemów ma dolną granicę złożoności liniowej?” pozostaje szeroko otwarty (w przypadku obwodów). Apeluję do wszystkich młodych badaczy: śmiało, te „bariery” nie są niezniszczalne! Ale spróbuj myśleć w „nienaturalny sposób”, w sensie Razborova i Rudicha.

— Stasys
źródło

Czy to jest praca Hastada z 1998 roku? nada.kth.se/~johanh/monotoneconnect.pdf Nie sądzę, że granica wiąże się z „nie”. Dodatkowo wykładnik jest kwadratowy.

— T ....

@JA: Nie, to jest w innym artykule z tego samego roku J. Håstad, The Shrinkage Exponent to 2, SIAM Journal on Computing, 1998, Vol 27, str. 48-64.

— Stasys

(3 + Ω (1)) n

$(3+\Omega(1))n$