Agrawal, Manindra (2002) Pseudo-random generators and structure of complete degrees Proceedings of 17th IEEE Annual Conference on Computational Complexity . pp. 113-121.
![]()
|
PDF
- Author Version
133kB |
Official URL: http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnum...
Related URL: http://dx.doi.org/10.1109/CCC.2002.1004349
Abstract
It is shown that, if there exist sets in E (the exponential complexity class) that require 2Ω(n)-sized circuits, then sets that are hard for class P (the polynomial complexity class) and above, under 1-1 reductions, are also hard under 1-1 size-increasing reductions. Under the assumption of the hardness of solving the RSA (Rivest-Shamir-Adleman, 1978) problem or the discrete log problem, it is shown that sets that are hard for class NP (nondeterministic polynomial) and above, under many-1 reductions, are also hard under (non-uniform) 1-1 and size-increasing reductions.
Item Type: | Article |
---|---|
Source: | Copyright of this article belongs to Proceedings of 17th IEEE Annual Conference on Computational Complexity. |
ID Code: | 92022 |
Deposited On: | 26 May 2012 13:52 |
Last Modified: | 19 May 2016 05:36 |
Repository Staff Only: item control page