No complete disjoint NP-pair conjecture
No complete disjoint NP-pair conjecture
A disjoint NP pair is a pair of disjoint languages in NP, and polynomial reduction between pairs maps the first component to the first and the second to the second. No complete disjoint NP-pair conjecture. There exist no complete disjoint NP pair with respect to polynomial reductions. The source presents this as a strengthening of the nonuniform finite consistency conjecture; oracle results give evidence in both directions.
Sources & referencesView supporting material
Primary source
Pavel Pudlak, “Incompleteness in the finite domain”, arXiv:1601.01487 (2017).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.