On the Structure of Valiants Complexity ClassesReportar como inadecuado

On the Structure of Valiants Complexity Classes - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Institut für Mathematik Zürich

Abstract : 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.

Keywords : Poset of degrees Structural complexity Algebraic theories of NP-completeness diagonalization Poset of degrees.

Autor: Peter Bürgisser -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados