AF: Small: Disjoint NP-Pairs and Structural Properties of Complete Sets

（不相交）NP对是复杂度类NP中的一对不相交的非空集合。研究不相交np对的动机是它们与公钥密码系统和命题证明系统的关系。特别是，NP-hard或p -不可分割np -对的存在性问题的答案告诉我们安全公钥密码系统是否存在的问题；最优命题证明系统的存在性暗示了完全np对的存在性。该项目将进一步研究p不可分割和完整的np -对，特别是它们是否可以从一个比任何已知的假设都弱的假设中推导出来，以及这些np -对的存在是否具有以前未知的强大后果。PI将检查复杂性理论中普遍（不）相信的假设，例如NP！=coNP和PH坍缩，并研究它们与p不可分和完全np对存在的关系。研究完全集的结构性质是非常重要的，因为它们使我们更好地理解各种复杂性类的计算能力，也可能导致复杂性理论中分离结果的证明。建议的项目将集中于完整集合的以下结构性质：-鲁棒性：如果从集合中取出一定数量的元素，完整集合仍然是完整的吗？-自动约简性：一个完整的集合是否通过不查询输入字符串的约简而减少到它自己？-有丝分裂：一个完整的集合可以分裂成两个完整的集合吗？拟议的项目旨在解决关于这些属性的悬而未决的问题，特别是那些对复杂性理论有重大影响的问题。例如，exp完备集对于真值表约简是否可自动约简？要解决这个问题，要么将EXP从PH中分离出来，要么将PSPACE从p中分离出来。拟议的项目将在一所西班牙裔服务机构实施，并将提高学生，特别是西班牙裔少数民族，对理论计算机科学以及计算机科学和工程的研究和学习的兴趣。该项目将成为计算机科学界正在进行的努力的一部分，以了解计算机的计算极限。该项目的所有成果将通过会议和期刊出版物广泛传播。

A (disjoint) NP-pair is a pair of disjoint, nonempty sets in the complexity class NP. The study of disjoint NP-pairs is motivated by their relations to public-key cryptosystems and to propositional proof systems. In particular, answers to questions about existence of NP-hard or P-inseparable NP-pairs informs us about the question of whether secure public-key cryptosystems exist; existence of complete NP-pairs is implied by existence of optimal propositional proof systems. This project will investigate P-inseparable and complete NP-pairs further, in particular whether they can be derived from a hypothesis that is weaker than any of the known ones, and whether existence of these NP-pairs have strong consequences that are unknown before. PI will examine commonly (dis)believed hypotheses in complexity theory such as that NP!=coNP and that PH collapses, and research on their relations to the existence of P-inseparable and complete NP-pairs.It is important to study structural properties of complete sets because they gives us a better understanding of the computational power of various complexity classes, and also might lead to proofs of separation results in complexity theory. The proposed project will focus on the following structural properties of complete sets: - Robustness: does a complete set remain complete if certain amount of elements are taken away from the set? - Autoreducibility: does a complete set reduce to itself via a reduction that does not query on the input string? - Mitoticity: can a complete set be split into two complete sets? The proposed project aims to address the remaining open questions regarding these properties especially those having major impact in complexity theory if settled. For example, are EXP-complete sets autoreducible for the truth-table reductions? Solving this problem would either separate EXP from PH, or PSPACE from P.The proposed project will be implemented at a Hispanic-serving institution and will promote interest among students, especially Hispanic minorities, for research and study in theoretical computer science and for computer science and engineering at large. The project will be part of the ongoing effort in the computer science community to understand the computation limits of computers. All results from the project will be disseminated broadly through conferences and journal publications.