English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 DetailsSummary
  On the Relative Power of Reduction Notions in Arithmetic Circuit Complexity

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

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-002C-4F8E-E Version Permalink: https://hdl.handle.net/11858/00-001M-0000-002C-4F8F-C
Genre: Paper

Files

show Files
hide Files
:
arXiv:1609.05942.pdf (Preprint), 125KB
View   Save
File Permalink:
https://hdl.handle.net/11858/00-001M-0000-002C-4F90-6
Name:
arXiv:1609.05942.pdf
Description:
File downloaded from arXiv at 2017-01-30 14:37
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
http://arxiv.org/help/license

Locators

show

Creators

show
hide
 Creators:
Ikenmeyer, Christian1, Author           
Mengel, Stefan2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Computational Complexity, cs.CC,
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2016-09-192016
 Publication Status: Published online
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1609.05942
URI: http://arxiv.org/abs/1609.05942
BibTex Citekey: IM:16
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show