Je pense qu'un théorème de hiérarchie des tailles pour la complexité des circuits peut être une percée majeure dans le domaine. Est-ce une approche intéressante de la séparation des classes? La motivation de la question est que nous devons dire il existe une fonction qui ne peut pas être calculée...
Les théorèmes de la hiérarchie sont des outils fondamentaux. Un bon nombre d'entre eux ont été rassemblés dans une question précédente (voir Quelles hiérarchies et / ou théorèmes de hiérarchie connaissez-vous? ). Certaines séparations de classes de complexité découlent directement des théorèmes de...
Quel genre de théorèmes de hiérarchie existe-t-il pour la profondeur du circuit? Des déclarations comme g(n)∈o(f(n))g(n)∈o(f(n))g(n) \in o(f(n))f(n)∈nO(1)f(n)∈nO(1)f(n) \in n^{O(1)}SizeDepth(nO(1),g(n))⊊SizeDepth(nO(1),f(n))SizeDepth(nO(1),g(n))⊊SizeDepth(nO(1),f(n))\mathsf{SizeDepth}(n^{O(1)},...
Question générale Le théorème de la hiérarchie spatiale se généralise-t-il au calcul non uniforme? Voici quelques questions plus spécifiques: L/poly⊊PSPACE/polyL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Pour toutes les fonctions constructibles spatiales f(n)f(n)f(n) ,...
Nous savons que . D'après le théorème de Savitch, , et, depuis Space Hierarchy Teorem, . Donc, comme nous ne savons pas si , nous ne savons pas si , ou savons-nous que ? Quelqu'un at-il essayé de prouver que \ mathcal L ^ 2 \ subseteq \ mathcal P ? Quels sont les derniers résultats ou efforts en ce...