ON THE POWER OF 2-LOCAL RANDOM REDUCTIONS

被引：5

作者：

FORTNOW, L

SZEGEDY, M

机构：

[1] Computer Science Department, University of Chicago, Chicago

来源：

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

基金：

美国国家科学基金会;

关键词：

COMPUTATIONAL COMPLEXITY;

D O I：

10.1016/0020-0190(92)90104-4

中图分类号：

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

学科分类号：

0812 ;

摘要：

We show that any language that has a two-locally-random reduction in which the target functions are boolean is in NP/poly and co-NP/poly. This extends and simplifies a result by Yao.

引用

页码：303 / 306

页数：4