On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity

Ikenmeyer, Christian; Mengel, Stefan

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

成果報告書

On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity

MPS-Authors

/persons/resource/persons202366

Ikenmeyer, Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:1609.05942.pdf
(プレプリント), 125KB

付随資料 (公開)

There is no public supplementary material available

引用

Ikenmeyer, C., & Mengel, S. (2016). On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity. Retrieved from http://arxiv.org/abs/1609.05942.

引用: https://hdl.handle.net/11858/00-001M-0000-002C-4F8E-E

要旨

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.