Ma question concerne les théorèmes 4.1 et 4.2 dans "Théorie de la complexité géométrique V" .
Le premier théorème indique qu'il existe un algorithme EXPSPACE pour construire hsop pour (voir les définitions dans l'article) sur C (en fait sur un champ arbitrairement fermé algébriquement de caractéristique zéro).
Le second fournit un algorithme Monte-Carlo probabiliste poly-temps pour le même problème.
Ces résultats peuvent-ils être étendus à une fermeture algébrique d'un champ fini?
Si je comprends bien, c'est possible parce que le problème de Nullstellensatz de Hilbert appartient à PSPACE dans ce cas également. Le théorème de Heintz et Schnorr est également valable pour les domaines de caractéristiques arbitraires ...