The Complexity of two Problems on Arithmetic Circuits

Abstract : By using arithmetic circuits, encoding multivariate polynomials may be drastically more efficient than writing down the list of monomials. Via the study of two examples, we show however that such an encoding can be hard to handle with a Turing machine even if the degree of the polynomial is low. Namely we show that deciding whether the coefficient of a given monomial is zero is hard for P^{#P} under strong nondeterministic Turing reductions. As a result, this problem does not belong to the polynomial hierarchy unless this hierarchy collapses. For polynomials over fields of characteristic k > 0, this problem is Mod_k P-complete. This gives a coNP^{Mod_k P} algorithm for deciding an upper bound on the degree of a polynomial given by a circuit in fields of characteristic k > 0.
Type de document :
Pré-publication, Document de travail
16 pages. 2007
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00167613
Contributeur : Sylvain Perifel <>
Soumis le : mardi 21 août 2007 - 18:07:44
Dernière modification le : mardi 16 janvier 2018 - 15:34:39
Document(s) archivé(s) le : jeudi 8 avril 2010 - 21:23:39

Fichiers

circuits.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00167613, version 1

Collections

Citation

Pascal Koiran, Sylvain Perifel. The Complexity of two Problems on Arithmetic Circuits. 16 pages. 2007. 〈ensl-00167613〉

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

129