Densité des langues P-complètes

Supposons que soit un langage booléen, de chaînes finies sur . Soit le nombre de chaînes de de longueur . Pour une fonction des entiers positifs aux nombres réels positifs, a une densité supérieure si pour tout suffisamment grand . $L$ $\{0,1\}$ $L_n$ $L$ $n$ $d(n)$ $L$ $d(n)$ $L_n \le 2^n d(n)$ $n$

Y a-t-il des langues booléennes P-complètes qui ont une densité supérieure ? $O(1/n)$

Motivation

PARITE a une densité supérieure . OUI (le langage de toutes les chaînes binaires finies) a une densité supérieure 1. Tout langage fini a une densité supérieure 0. $1/2$
Un langage clairsemé a la propriété qu'il existe un polynôme tel que pour tout . Si est une langue clairsemée, alors pour un polynôme de degré un supérieur à celui de , donc la densité supérieure de est nulle. $L$ $p(n)$ $L_n - L_{n-1} \le p(n)$ $n$ $L$ $L_n \le p_1(n)$ $p_1$ $p$ $L$
Jin-Yi Cai et D. Sivakumar ont montré qu'un langage P-complet ne peut être rare que si P = L (= LOGSPACE). Puisque P = co-P, tout langage dont le complément est rare ne peut pas non plus être P-complet, sauf si P = L.
Par une simple inégalité (voir par exemple Corollaire 2 de Rosser et Schoenfeld 1962 ), PRIMES a une densité supérieure . Question Les problèmes PRIMES, FACTORING sont-ils connus pour être P-dur? discute si PRIMES est P-hard (cela semble être ouvert actuellement). $(\log_2 e)/n$
Dans un certain sens, les langages complets (ou universels) d'une classe de complexité contiennent toute la structure de la classe. Donc, mon hypothèse provisoire, basée sur une extrapolation sauvage du résultat de Cai et Sivakumar, serait que de telles langues ne peuvent pas être trop clairsemées. La borne polynomiale habituelle définissant des langues clairsemées semble trop restrictive, donc je pose une question sur une borne un peu moins restrictive.

Les travaux sur la faiblesse de Fortnow, Hemaspaandra et d'autres sont peut-être également liés.

La question peut être posée à des classes autres que P, mais je ne me souviens d'aucun résultat qui permettrait d'établir une densité de, disons, -SAT. Des pointeurs vers la littérature pertinente seraient les bienvenus. $k$

Remerciements

Voir aussi la question connexe Densité conditionnelle des nombres premiers . Merci à @Tsuyoshi Ito et @Kaveh pour leurs commentaires utiles sur une version antérieure de cette question, qui était malheureusement mal posée.

cc.complexity-theory reference-request p-hardness András Salamon
la source

Je pense que

(ou une autre fraction polynomiale) a trop de chaînes, la meilleure question est de poser des questions sur les limites supérieures et inférieures.

2^{n} / n

$2^n/n$

Kaveh

Réponses:

Je ne sais pas quelle est la densité des problèmes P-complets courants, mais voici un argument de remplissage qui montre comment abaisser une densité inférieure à : $1/n$

Prenez votre langue P-complete préférée . Cette langue a une certaine densité . Définissons maintenant . En général, sera une fonction de , donc cela pourrait ne pas définir $L_n \subseteq \{0,1\}^n$ $d(n) \in \omega(1/n)$ $L'_{n + m} = \{x0^m | x \in L_n\}$ $m$ $n$ $L'$ pour toutes les tailles, puisque nous ne nous soucions que de la densité supérieure, il suffit de faire si . Quelle est la densité supérieure de ? Eh bien, nous avons $L'_k = \emptyset$ $k \neq n + m$ $L'$

{ré}^{'} (n + m) = \frac{| L_{n + m}^{'} |}{2^{n + m}} = \frac{| L_{n} |}{2^{n + m}} \leq \frac{ré (n)}{2^{m}}

$d'(n + m) = \frac{|L'_{n + m}|}{2^{n + m}} = \frac{|L_n|}{2^{n + m}} \leq \frac{d(n)}{2^m}$

Utilisons maintenant les réductions de LOG pour construire une machine pour utilisant une machine pour . Eh bien, si vous avez une entrée copiez-la simplement un bit à la fois sur la bande de requête (utilisez également un compteur pour compter ce que est), puis utilisez un deuxième compteur pour compter jusqu'à , en ajoutant un chaque chaque fois que vous ajoutez un zéro à la bande de requête (pour avoir un espace de journal, nous avons besoin de et facilement calculable). Ensuite, interrogez et renvoyez le résultat comme réponse. $M$ $L$ $M'$ $L'$ $x$ $n$ $m(n)$ $m(n) \in poly(n)$

Si nous voulons être sûrs que nous sommes inférieurs à il suffit de choisir , et alors nous aurons . $1/n$ $m(n) = n$ $d'(2n) \leq d(n)/2^n \in O(1/n)$

Artem Kaznatcheev
la source

Merci, cela répond à la question. Cet argument semble reposer sur

étant polynomialement lié à

- la densité supérieure

serait-elle réalisable?

m

$m$

n

$n$

1 / \log n

$1/\log n$

András Salamon,

Je pense que oui, vous auriez juste besoin de m = log log n. En général, pour m = f (n), vous pouvez choisir n'importe quel f qui est dans l'espace LOG (avec n en unaire). (ou NC si vous préférez ces réductions).

Artem Kaznatcheev