Je veux savoir si la non-uniformité aide les fonctions informatiques dans la pratique. Il est facile de montrer qu'il existe des fonctions dans , de prendre n'importe quelle fonction non calculable f et de considérer le langage { 0 f ( n ) : n ∈ ω }, qui a clairement des circuits non uniformes simples, mais n'est pas du tout calculable de manière uniforme, mais ce n'est pas le genre de fonctions qui m'intéresse.
Existe-t-il une fonction que nous savons qu'elle peut être calculée de manière non uniforme, mais nous ne savons pas si elle peut être calculée de manière uniforme (ou du moins prouver qu'elle ne peut pas être calculée de manière uniforme n'est pas évidente)?
Comment la non-uniformité des circuits peut-elle être utilisée pour calculer des fonctions dont on ne sait pas qu'elles peuvent être calculées de manière uniforme (avec presque la même quantité de ressources)?
Veuillez noter que je ne veux pas de fonctions pathologiques comme celles non calculables mentionnées ci-dessus, je veux des fonctions naturelles que les gens s'intéressent vraiment à l'informatique et il est plausible que cela puisse ou pourrait avoir été calculé uniformément.
Edit: je sais que . Donc, une réponse qui n'est pas un résultat de dérandomisation est plus intéressante pour moi.
Edit 2: Comme András Salamon et Tsuyoshi Ito l'ont dit dans leurs réponses, , et il y a des problèmes intéressants dans S p a r s e qui ne sont pas connus pour être en P , si formellement ils ont répondu à ce que j'ai demandé, mais cela ne l' aide avec ce que je suis vraiment intéressé par car la raison pour laquelle ils sont en P / p o l y est la possibilité de coder en dur une langue rare dans le circuit. Une langue qui n'est pas rare serait plus intéressante.
Réponses:
Je ne sais pas si cela répond à vos exigences, mais le billet de blog de Bill Gasarch en juillet 2010 pose des questions sur les langues dans SPARSE ∩NP qui ne sont pas supposées être en P, en donnant un exemple de Ramsey Theory. Ces langues appartiennent à (P / poly) ∩NP.
En relation avec cela, pour toute langue L ∈NP, la langue T L = {1 n : L contient une chaîne de longueur n } est en TALLY ∩NP ⊆ SPARSE∩NP ⊆ (P / poly) ∩NP. Selon le choix de la langue L , T L peut ne pas avoir de raison évidente d'appartenir à P.
la source
La formulation élégamment clairsemée de Tsuyoshi Ito dans une autre réponse ne le dit pas explicitement, mais cela vaut peut-être la peine d'être souligné: tout langage clairsemé est en P / poly. Ensuite, tout langage de pointage est en P / poly (car chaque langage de pointage est rare).
Donc, une façon de trouver des langues "naturelles" en P / poly mais pas en P, est de chercher des langues rares "dures". Comme vous le faites remarquer, les "plus difficiles" sont les indécidables lorsqu'ils sont encodés de manière clairsemée, par exemple en unaire. Plus généralement, la version codée unaire de toute langue en dehors de EXP sera alors en dehors de P. (Sinon, considérons la machine de Turing à temps exponentiel qui génère le codage unaire, composée avec la machine qui résout la langue codée unaire résultante dans le temps qui est polynomial dans le codage unaire. Ceci est exponentiel dans la taille de l'instance d'origine. La machine globale s'exécute ensuite en temps exponentiel.) Un langage pratique 2-EXP-complet pourrait alors convenir à votre goût comme un problème "naturel".
Notez que le langage théorique de Ramsey de Bill Gasarch semble tomber dans la catégorie des langues construites en sparsifiant un langage dur. Si l'on code l'instance comme un triple de nombres binaires au lieu de deux unaires et un binaire, alors la coloration n'est plus de taille polynomiale, donc le langage n'est pas évidemment en NP.
la source
Cela ressemble plus à un commentaire en réponse à la question révisée (révision 3) qu'à une réponse, mais c'est trop long pour un commentaire.
Il ne suffit pas d'exclure des langues rares pour exclure des langues comme { x ∈ {0,1} * : | x | ∈ S } au lieu de {1 n : n ∈ S }, où S est un sous-ensemble infini de {0, 1, 2,…}. Je voudrais souligner qu'il peut être difficile de distinguer le cas où une langue appartient à P / poly car elle est «essentiellement clairsemée» (comme {1 n : n ∈ S } et { x : | x | ∈ S}) et le cas où une langue appartient à P / poly pour d'autres raisons. La chose problématique ici est, évidemment, comment définir le terme «essentiellement clairsemé».
Vous voudrez peut-être définir le terme «éparses essentielles» comme suit: une langue est essentiellement clairsemée si elle est réductible à une langue clairsemée. Cependant, il faut faire attention car si vous utilisez la réductibilité de Turing à temps polynomial dans cette définition, la définition est équivalente à l'appartenance à P / poly!
Donc, une chose évidente à essayer est d'utiliser la réductibilité plusieurs à un polynôme. Je ne sais pas si cela équivaut à l'appartenance à P / poly, et encore moins si P / poly contient un langage naturel qui n'est pas essentiellement clairsemé dans ce sens.
la source