A 2.5n lower bound on the monotone network complexity of T 3 n期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

A 2.5n lower bound on the monotone network complexity of T 3 n

Authors:	Paul E. Dunne

Affiliation:	(1) Department of Computer Science, University of Warwick, CV47AL Coventry, Great Britain

Abstract:	Summary The k-th threshold function, T_kⁿ, is defined as: $T_k^n left( {x_1 ,...,x_n } right) = left{ begin{gathered} 1 if sumlimits_{i = 1}^n {x_i geqq k} hfill 0 otherwise hfill end{gathered} right.$ where x_i{0,1} and the summation is arithmetic. We prove that any monotone network computing T_3/n(x₁,...,x_n) contains at least 2.5n-5.5 gates.This research was supported by the Science and Engineering Research Council of Great Britain, UK

Keywords:
本文献已被 SpringerLink 等数据库收录！