ON THE COMPLEXITY OF FINITE RANDOM FUNCTIONS

被引：5

作者：

FEIGE, U

机构：

[1] Department of Applied Mathematics, The Weizmann Institute, Rehovot

来源：

INFORMATION PROCESSING LETTERS | 1992年 / 44卷 / 06期

关键词：

COMPUTATIONAL COMPLEXITY; RANDOM FUNCTIONS;

D O I：

10.1016/0020-0190(92)90102-2

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We describe a method for relating the complexity of random finite functions to the complexity of the most complex finite functions. Using this method we derive an alternative proof for a known OMEGA(n log n) lower bound on the depth of noisy Boolean decision trees that compute random functions.

引用

页码：295 / 296

页数：2