Learning deep Architectures for AI ftml_book Page

这篇文章直切主题，应该有比较完整的证明。有些问题总想追根问源，我得看看。

这个结果来自1994年Godel prize的论文：Johan Håstad, "Almost optimal lower bounds for small depth circuits," Advances in Computing Research 5 (1989), 143-170.
是理论计算机领域的证明，方法据说很精巧，抱歉我没读过。

我也是这么想的，感谢你的指教，本以为豆瓣上没人会理会的，你的回答让我觉得这个社区还是挺活跃的，而且你也很耐心认真地讨论，这种素养难能可贵，咱们社会需要更多你这样的人材，活跃求知求真的气氛。跟你交流很愉快，Thank u very much!

我不保证我举的例子就是对的，但是我的看法是，在我们不知道这个逻辑运算具体表达式（比如 A and B or C）的时候，我们确实是要通过枚举去“表示”（注意是表示，或者叫唯一确定一个函数f(A, B, C)）而不是“计算”；而用两层结构表示的话，就是俩逻辑运算符号。可能我之前的说法有些问题，一个讲了计算一个讲了表示。
可能另一个从“计算次数”来讲比较合适的例子是秦九韶算法？不过从层数来增加了不少……

如果你把规模用运算的次数来衡量的话，两种表示方式都做3次运算（判断3个变量的真值）即可，就枚举来说，只要三个值确定，对应的结果也就确定了。断不出熟优熟劣！

1. (A and B) or C, 括号内是第一层，括号外是第二层，从这个角度，你只需要判断C是否为真，以及C为假时A和B是否都为真，理论上至多只要3次运算；
2. 一层表示，例如枚举的话，你需要枚举出(A, B, C)的所有真值组合（共8个），然后对应给输出，例子：
(T, T, T) -> T; (T, F, F) -> F; (T, F, T) -> T

对这个论点的理解，文章后面还是有不少解析的，也有不少例子，例如逻辑表达式，多项式的表示。但是对你举的这个例子：你说的逻辑运算是指如何表示结果，还是指其他的？ A and B or C，用两层架构表示，怎样表示？用枚举怎么表示？ 可能是我的更解方向上跟你的意思有偏差，还请不吝赐教。

你可以考虑一下逻辑运算，比如 A and B or C，它可以用一个两层架构表示，但是如果要用一层表示，比如枚举，要得到所有结果需要枚举8次。