Pi-Sigma-Pi threshold formulas

被引：0

作者：

Radhakrishnan, J ^{[1
]}

机构：

[1] JAPAN ADV INST SCI & TECHNOL,SCH INFORMAT SCI,HOKURI KU,TATSUNOKUCHI,ISHIKAWA 92312,JAPAN

来源：

MATHEMATICAL SYSTEMS THEORY | 1996年 / 29卷 / 04期

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present lower and upper bounds on the size of pi-sigma-pi (Pi Sigma Pi) formulas computing threshold functions for small thresholds. Our results show that the limitations of Pi Sigma Pi formulas for computing threshold functions for small thresholds are more pronounced than suggested by the lower bounds for small depth circuits computing the majority function.

引用

页码：357 / 374

页数：18

共 8 条

[1] THRESHOLD FUNCTIONS AND BOUNDED DEPTH MONOTONE CIRCUITS
BOPPANA, RB
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1986, 32 (02) : 222 - 229
[2] BOPPANA RB, 1989, ADV COMPUTING RES, V5, P27
[3] HANSEL G, 1964, CR HEBD ACAD SCI, V258, P6037
[4] HASTAD J, 1989, ADV COMPUTING RES, V5, P143
[5] Krichevskii R.E, 1964, SOV PHYS DOKL, V8, P770
[6] SIGMA-PI-SIGMA-THRESHOLD FORMULAS
RADHAKRISHNAN, J
[J]. COMBINATORICA, 1994, 14 (03) : 345 - 374
[7] RADHAKRISHNAN J, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P314, DOI 10.1109/SFCS.1991.185384
[8] [No title captured]

← 1 →