On the Existence of Complete Disjoint NP-Pairs

Author

Beyersdorff, Olaf

Author_Institution

Inst. fur Inf., Humboldt-Univ. zu Berlin, Berlin, Germany

fYear

2009

fDate

26-29 Sept. 2009

Firstpage

282

Lastpage

289

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/SYNASC.2009.9

Filename

5460837