论文标题
关于布尔read-k和多线性电路的注释
Notes on Boolean Read-k and Multilinear Circuits
论文作者
论文摘要
如果通过算术（纯粹是统计的）（纯粹是语法上），该电路的单调布尔（或和和）电路计算单调布尔函数F是一个读取的电路F，则该电路的算术（纯粹是语法上）具有f的属性（+，X）版本具有F的每个质量，f prient of f evernomial具有至少一个单个单单元素，其中至少包含一个与variables相同的一组，最多可用于k.每个单调电路都是一些k的读取电路。 We show that already read-1 (OR,AND) circuits are not weaker than monotone arithmetic constant-free (+,x) circuits computing multilinear polynomials, are not weaker than non-monotone multilinear (OR,AND,NOT) circuits computing monotone Boolean functions, and have the same power as tropical (min,+) circuits solving combinatorial minimization problems.最后，我们表明读取2（或和）电路可能比Read-1（或）电路要小。
A monotone Boolean (OR,AND) circuit computing a monotone Boolean function f is a read-k circuit if the polynomial produced (purely syntactically) by the arithmetic (+,x) version of the circuit has the property that for every prime implicant of f, the polynomial contains at least one monomial with the same set of variables, each appearing with degree at most k. Every monotone circuit is a read-k circuit for some k. We show that already read-1 (OR,AND) circuits are not weaker than monotone arithmetic constant-free (+,x) circuits computing multilinear polynomials, are not weaker than non-monotone multilinear (OR,AND,NOT) circuits computing monotone Boolean functions, and have the same power as tropical (min,+) circuits solving combinatorial minimization problems. Finally, we show that read-2 (OR,AND) circuits can be exponentially smaller than read-1 (OR,AND) circuits.
