On P-immunity of nondeterministic complete sets

机译：关于不确定集合的P-免疫

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

We show that every m-complete set for NEXP as well as its complement have an infinite subset in P. This answers an open question first raised by L. Berman (1976).

机译：我们证明NEXP的每个m-完整集及其补集在P中都有一个无限子集。这回答了L. Berman（1976）首先提出的一个开放性问题。

著录项

来源
《Structure in Complexity Theory Conference, 1995., Proceedings of Tenth Annual IEEE》|1995年|P.262-263|共2页
会议地点
作者
Tran N.;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类无线电电子学、电信技术;
关键词

相似文献

外文文献
中文文献
专利

1. Complete model-based equivalence class testing for nondeterministic systems [J] . Huang Wen-ling, Peleska Jan Formal Aspects of Computing . 2017,第2期

机译：针对不确定性系统的完整基于模型的等效类测试
2. Nondeterministic fuzzy automata with membership values in complete residuated lattices [J] . Pan Haiyu, Li Yongming, Cao Yongzhi, 高分子論文集 . 2017,第MARa期

机译：具有完全剩余格中隶属度值的非确定性模糊自动机
3. Proof of Nondeterministic Polynomial-Time Complete Problem for Soil Slope-Stability Evaluation [J] . Tang Huiming, Liu Xiao, Xiong Chengren, International journal of geomechanics . 2016,第5期

机译：边坡稳定性评估的不确定多项式时间完全问题的证明
4. On P-immunity of nondeterministic complete sets [C] . Tran N., Institute of Electric and Electronic Engineer Annual IEEE Structure in Complexity Theory Conference . 1995

机译：论非法完成全套的P-IMP
5. Complete set of one qubit quantum gates using twisted rapid passage. [D] . Hoover, Melique. 2010

机译：使用扭曲的快速通道的一个量子比特量子门的完整集合。
6. Communication: A novel implementation to compute MP2 correlation energies without basis set superposition errors and complete basis set extrapolation [O] . Anant Dixit, Julien Claudot, Sébastien Lebègue, -1

机译：通信：一种新颖的实现可计算MP2相关能量而无基集叠加误差和完整的基集外推
7. On P-immunity of nondeterministic complete sets [O] . Nicholas Tran 1995

机译：关于非确定性成套的p-免疫
8. Making use of optimization, nondeterministic analysis, and numerical simulation to assess firing set robustness in a fire [R] . Romero, V. J. 1996

机译：利用优化，非确定性分析和数值模拟来评估火灾中的点火设置稳健性

On P-immunity of nondeterministic complete sets

摘要

著录项

相似文献

相关主题

期刊订阅