Geodesic
On the Structure of Valiant's Complexity Classes
Discrete mathematics & theoretical computer science, Tome 3 (1998-1999) no. 3.

Voir la notice de l'article provenant de la source Episciences

In Valiant developed an algebraic analogue of the theory of NP-completeness for computations of polynomials over a field. We further develop this theory in the spirit of structural complexity and obtain analogues of well-known results by Baker, Gill, and Solovay, Ladner, and Schöning.\par We show that if Valiant's hypothesis is true, then there is a p-definable family, which is neither p-computable nor \textitVNP-complete. More generally, we define the posets of p-degrees and c-degrees of p-definable families and prove that any countable poset can be embedded in either of them, provided Valiant's hypothesis is true. Moreover, we establish the existence of minimal pairs for \textitVP in \textitVNP.\par Over finite fields, we give a \emphspecific example of a family of polynomials which is neither \textitVNP-complete nor p-computable, provided the polynomial hierarchy does not collapse.\par We define relativized complexity classes VP^h and VNP^h and construct complete families in these classes. Moreover, we prove that there is a p-family h satisfying VP^h = VNP^h. 
@article{DMTCS_1999_3_3_a3,
     author = {B\"urgisser, Peter},
     title = {On the {Structure} of {Valiant's} {Complexity} {Classes}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {3},
     number = {3},
     year = {1998-1999},
     doi = {10.46298/dmtcs.260},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.260/}
}
TY  - JOUR
AU  - Bürgisser, Peter
TI  - On the Structure of Valiant's Complexity Classes
JO  - Discrete mathematics & theoretical computer science
PY  - 1998-1999
VL  - 3
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.260/
DO  - 10.46298/dmtcs.260
LA  - en
ID  - DMTCS_1999_3_3_a3
ER  - 
%0 Journal Article
%A Bürgisser, Peter
%T On the Structure of Valiant's Complexity Classes
%J Discrete mathematics & theoretical computer science
%D 1998-1999
%V 3
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.260/
%R 10.46298/dmtcs.260
%G en
%F DMTCS_1999_3_3_a3
Bürgisser, Peter. On the Structure of Valiant's Complexity Classes. Discrete mathematics & theoretical computer science, Tome 3 (1998-1999) no. 3. doi : 10.46298/dmtcs.260. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.260/

Cité par Sources :