Title :
On the Existence of Complete Disjoint NP-Pairs
Author :
Beyersdorff, Olaf
Author_Institution :
Inst. fur Inf., Humboldt-Univ. zu Berlin, Berlin, Germany
Abstract :
Disjoint NP-pairs are an interesting model of computation with important applications in cryptography and proof complexity. The question whether there exists a complete disjoint NP-pair was posed by Razborov in 1994 and is one of the most important problems in the field. In this paper we prove that there exists a many-one hard disjoint NP-pair which is computed with access to a very weak oracle (a tally NP-oracle).In addition, we exhibit candidates for complete NP-pairs and apply our results to a recent line of research on the construction of hard tautologies from pseudorandom generators.
Keywords :
computational complexity; public key cryptography; complete disjoint NP-pair; cryptography; hard tautology; many-one hard disjoint NP-pair; proof complexity; pseudorandom generator; public-key cryptosystem; tally NP-oracle; weak oracle; Computational modeling; Computer applications; Polynomials; Public key cryptography; Scientific computing; Security; Sufficient conditions; disjoint NP-pairs; proof complexity generators;
Conference_Titel :
Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2009 11th International Symposium on
Conference_Location :
Timisoara
Print_ISBN :
978-1-4244-5910-0
Electronic_ISBN :
978-1-4244-5911-7
DOI :
10.1109/SYNASC.2009.9
