MetadataShow full item record
The primary topic of this dissertation is disjoint NP-pairs. A disjoint NP-pair is a pair of disjoint, nonempty sets in NP. The study of disjoint NP-pairs is motivated by its connections to secure public-key Cryptosystems and to propositional proof complexity. One fundamental question in the study of disjoint NP-pairs is whether there exist P-inseparable or NP-hard disjoint NP-pairs. This question is closely related to the existence of secure public-key cryptosystems. Another important question on disjoint NP-pairs is whether the class of all disjoint NP-pairs has a complete pair. A negative answer to this question would imply non-existence of optimal propositional proof systems, which is a well-studied but still open question in proof theory. We study these questions and obtain results that give better understandings of these questions, as well as the relations between disjoint NP-pairs and propositional proof systems. In particular, we show that the above questions cannot be settled with relativizable techniques. It has been recently known that the degree structure of disjoint NP-pairs is identical to the degree structure of canonical NP-pairs of propositional proof systems. This makes it interesting and important to study the degree structure of disjoint NP-pairs. We study this and prove that the degree structure of disjoint NP-pairs is "universal'' in the sense that every countable distributive lattice can be embedded into every interval of degrees of disjoint NP-pairs by maps that preserve the least or greatest elements. We also study the question how much information canonical NP-pairs contain of their corresponding propositional proof systems. We obtain various results demonstrating that canonical NP-pairs reflect the properties of their corresponding propositional proof systems, but only to certain extent. The secondary topic of this dissertation is structural properties of complete sets. What structural properties complete sets of different complexity classes have is a basic problem in computational complexity. It is important to study such computational structure of complete sets, because they, by reductions of all the sets in the class to the complete sets, represent all of the structure that a class might have. For this reason, the study of structural properties of complete sets gave us a better understanding of the computational power of various complexity classes, and also might lead to proofs of separation results in complexity theory. We mainly study robustness, autoreducibility, and mitoticity of complete sets. In particular we solve the open question whether polynomial 2-tt autoreducibilty implies polynomial-time 2-tt mitoticity.