ausblenden:
Schlagwörter:
Computer Science, Computational Complexity, cs.CC,
Zusammenfassung:
We show that the two main reduction notions in arithmetic circuit complexity,
p-projections and c-reductions, differ in power. We do so by showing
unconditionally that there are polynomials that are VNP-complete under
c-reductions but not under p-projections. We also show that the question of
which polynomials are VNP-complete under which type of reductions depends on
the underlying field.
