On the limits of gate elimination

作者：

Highlights：

• Gate elimination with O(1) circuit complexity decrease only proves O(n) lower bounds.

• Circuit complexity is reduced by O(1) after O(1) arbitrary substitutions.

• Subadditive complexity is reduced by O(1) after O(1) arbitrary substitutions.

• Gate elimination counting gates and inputs cannot prove a bound of cn for explicit c.

摘要

•Gate elimination with O(1) circuit complexity decrease only proves O(n) lower bounds.•Circuit complexity is reduced by O(1) after O(1) arbitrary substitutions.•Subadditive complexity is reduced by O(1) after O(1) arbitrary substitutions.•Gate elimination counting gates and inputs cannot prove a bound of cn for explicit c.

论文关键词：Circuit complexity,Lower bounds,Gate elimination

论文评审过程：Received 27 April 2017, Revised 1 January 2018, Accepted 30 April 2018, Available online 26 May 2018, Version of Record 31 May 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2018.04.005