
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.
Algebraic theories of NP-completeness diagonalization, Poset of degrees, structural complexity, poset of degrees., [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Poset of degrees., algebraic theories of np-completeness diagonalization, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], QA1-939, Complexity classes (hierarchies, relations among complexity classes, etc.), Structural complexity, poset of degrees, algebraic theories of NP-completeness diagonalization, Mathematics
Algebraic theories of NP-completeness diagonalization, Poset of degrees, structural complexity, poset of degrees., [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Poset of degrees., algebraic theories of np-completeness diagonalization, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], QA1-939, Complexity classes (hierarchies, relations among complexity classes, etc.), Structural complexity, poset of degrees, algebraic theories of NP-completeness diagonalization, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
