Pseudo-random generators and structure of complete degrees

被引：21
|
作者：
Agrawal, M [1 ]
机构：
[1] Indian Inst Technol, Dept CSE, Kanpur 208016, Uttar Pradesh, India
来源：
17TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2002年
关键词：
D O I：
10.1109/CCC.2002.1004349
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
It is shown that if there exist sets in E that require 2(Omega(n))-sized circuits then sets that are hard for class P, and above, under 1-1 reductions are also hard under 1-1, size-increasing reductions. Under the assumption of the hardness of solving RSA or Discrete Log problem, it is shown that sets that are hard for class NP, and above, under many-one reductions are also hard under (non-uniform) 1-1, and size-increasing reductions.
引用
收藏
页码：139 / 147
页数：9
相关论文
共 50 条
12345