Existe-t-il une borne inférieure meilleure que linéaire pour l'affacturage et le log discret?

Y a-t-il des références qui fournissent des détails sur les limites inférieures du circuit pour des problèmes difficiles spécifiques survenant en cryptographie tels que l'affacturage entier, problème de logarithme discret premier / composite et sa variante sur un groupe de points de courbes elliptiques (et leurs variétés abéliennes de dimension supérieure) et le général problème de sous-groupe caché?

Plus précisément, l'un de ces problèmes a-t-il plus qu'une limite linéaire de complexité linéaire?

cc.complexity-theory complexity-classes cr.crypto-security circuit-complexity contre
la source

Vous savez, bien sûr, qu'aucune borne inférieure meilleure que 5n pour la complexité du circuit n'est connue, pour <i> toute </i> fonction explicite, pas seulement pour celles que vous avez mentionnées. Donc, vous devez spécifier la question. De meilleures limites ne sont connues que pour les circuits restreints . Vous pourriez peut-être trouver des réponses partielles sur la page d'accueil de <a href=" web.science.mq.edu.au/~igor "rel="nofollow"> Igor Sparlinski. </a>

Stasys

Eh bien, je ne sais pas trop ce que tu veux dire par "ce fait intéressant". Quoi qu'il en soit, l'état de l'art actuel en matière de complexité des circuits est donné dans mon prochain livre thi.informatik.uni-frankfurt.de/~jukna/BFC-book . Utilisateur: ami Mot de passe: catchthecat

Stasys

@Stasys, je me souviens qu'un étudiant russe a parlé de la limite inférieure du formulaire 7n + O (1) basée sur l'élimination des portes à l'école d'automne de Prague il y a deux ans, mais je ne me souviens plus de détails.

Kaveh

Kaveh, c'est une borne inférieure a (7/3) nc, pas 7n. Cela a été prouvé par Arist Kojevnikov et Sasha Kulikov de Petersburg. L'avantage de leur preuve est sa simplicité, non numérique. Plus tard, ils ont donné une simple preuve de 3n-o (1) borne inférieure pour les circuits généraux (toutes les portes fanin-2 sont autorisées). Quoique pour des fonctions très compliquées - disperseurs affines. Les articles sont en ligne à: logic.pdmi.ras.ru/~kulikov/papers . En fait, Redkin (1973) a montré des limites serrées 7n-7 pour la fonction de parité, mais seulement si seules les portes NOT et AND sont autorisées. Si également OU est autorisé, alors sa limite est 4n-4 (également serrée!).

Stasys

@StasysJukna: une combinaison de vos commentaires est appropriée comme réponse.

Suresh Venkat

Réponses:

@Suresh: suivant vos conseils, voici ma "réponse". L'état des bornes inférieures du circuit est assez déprimant. Voici les "records actuels":

$4n-4$ pour les circuits sur et pour les circuits sur et computing ; Redkin (1973). Ces limites sont serrées. $\{\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)$ pour les circuits sur la base avec toutes les portes fanin-2, sauf la parité et sa négation; Iwama et Morizumi (2002).
$3n-o(n)$ pour les circuits généraux sur la base avec toutes les portes fanin-2; Blum (1984). Arist Kojevnikov et Sasha Kulikov de Petersburg ont trouvé une preuve plus simple d'une borne inférieure . L'avantage de leur preuve est sa simplicité, non numérique. Plus tard, ils ont donné une simple preuve de borne inférieure pour les circuits généraux (toutes les portes fanin-2 sont autorisées). Quoique pour des fonctions très compliquées - disperseurs affines. Les articles sont en ligne ici . $(7/3)n-o(1)$ $3n-o(1)$
$n^{3-o(1)}$ pour les formules sur ; Hastad (1998). $\{\land,\lor,\neg\}$
$\Omega(n^2/\log n)$ pour les formules générales de fanin- , pour les programmes de branchement déterministe et pour les programmes de branchement non déterministes; Nechiporuk ~ (1966). $2$ $\Omega(n^2/\log^2 n)$ $\Omega(n^{3/2}/\log n)$

Donc, votre question "Plus précisément, l'un de ces problèmes a-t-il plus qu'une limite linéaire de complexité linéaire?" reste largement ouvert (dans le cas des circuits). Mon appel à tous les jeunes chercheurs: allez-y, ces "barrières" ne sont pas incassables! Mais essayez de penser d'une «manière non naturelle», au sens de Razborov et Rudich.

Stasys
la source

Est-ce le papier de Hastad de 1998? nada.kth.se/~johanh/monotoneconnect.pdf Je ne pense pas que la limite implique «non». De plus, l'exposant est quadratique.

T ....

@JA: Non, c'est dans un autre de ses articles de la même année J. Håstad, The Shrinkage Exponent is 2, SIAM Journal on Computing, 1998, Vol 27, pp 48-64.

Stasys

Il semble que personne n'ait mis à jour cette réponse avec les nouveaux résultats, alors je vais le faire ici. L'article de 2015 de Magnus Find, Alexander Golovnev, Edward A. Hirsch et Alexander S. Kulikov «A Better-than-3n Lower Bound for the Circuit Complexity of an Explicit Function». donne une limite inférieure . Peut-être que cela rend les choses un peu moins déprimantes.

(3 + Ω (1)) n

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

Manu