EXP复杂性与伪随机性的平均情况转换
"这篇论文是关于复杂性理论中伪随机性、平均情况复杂性和最坏情况复杂性之间关系的研究,特别是在EXP复杂性类的上下文中。作者Luca Trevisan和Salil Vadhan在2006年的文章中探讨了如何从一致约简的角度构建伪随机生成器,并建立了最坏情况到平均情况的最优连接。" 文章首先介绍了Impagliazzo和Wigderson先前的工作,他们利用一致复杂性假设(EXP=BPP)构造了伪随机生成器,但没有提供最坏情况与伪随机性之间的连续权衡,也没有明确涉及平均情况的硬度结果。 论文的核心贡献在于,作者证明了如果EXP等于BPTIME(t(n)),那么对于n个输入长度的EXP问题,无法在输入的分数n1/2+1/t'(n)上使用BPTIME(t'(n))的算法进行有效解决,这里的t'与t不相等。这个结果展示了从最坏情况到平均情况的转换,优化了之前对问题复杂性的理解。 此外,论文还提出并证明了一个PSPACE-完全的自校正和向下自约问题,这个结果简化并强化了IW2(Impagliazzo和Wigderson)的证明。作者指出,他们的方法和IW2的方法不能仅仅通过“黑箱”一致约简来证明,这暗示了他们在方法上的创新和独特性。 文章进一步讨论了过去20年间复杂性理论研究的焦点,即伪随机性、平均硬度和最坏硬度之间的关系。在非均匀环境下,已经证明了这三个概念的等价性,即高最坏情况复杂性问题的存在、高平均情况复杂性问题的存在以及强伪随机生成器的可构造性是相互关联的。然而,对于较低复杂度的电路,如超多项式时间,这种等价性的量化关系变得更加紧密。 在结论部分,作者可能讨论了这些发现对于理论计算机科学的潜在影响,包括如何通过平均情况复杂性的理解来推进伪随机生成器的设计,以及这如何可能影响我们对EXP类问题理解和模拟的能力。此外,这些结果也可能对密码学、安全性和计算复杂性理论的其他领域有深远的影响。
![](https://csdnimg.cn/release/download_crawler_static/88790167/bg5.jpg)
剩余24页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
- 粉丝: 5
- 资源: 2万+
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)