Separating OR, SUM, and XOR circuits
详细信息    查看全文
文摘

We study circuits for linear maps defined by n times n Boolean matrices.

We consider three circuit models: OR-circuits, SUM-circuits, and XOR-circuits.

Our focus is on separating these models in terms of their circuit complexities.

We obtain matrices with OR-circuits of size O(n) which require large SUM-circuits.

We prove a conditional quadratic lower bound for an OR–XOR circuit rewriting task.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700