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

19

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?

cc.complexity-theory complexity-classes cr.crypto-security circuit-complexity vs
źródło
9
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
8
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
1
@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
12
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,
5
@StasysJukna: kombinacja twoich komentarzy jest odpowiednia jako odpowiedź.
Suresh Venkat

Odpowiedzi:

26

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

  • 4n−4{∧,∨,¬}7n−7{∧,¬}{∨,¬}⊕n(x)=x1⊕x2⊕⋯⊕xn
  • 5n−o(n)
  • 3n−o(n)(7/3)n−o(1)3)n-o(1)
  • n3)-o(1){∧,∨,¬}
  • Ω(n2)/log⁡n)2)Ω(n2)/log2)⁡n)Ω(n3)/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