article

Tuples of Disjoint $\mathsf{NP}$-Sets

Author:

Olaf BeyersdorffAuthors Info & Claims

Theory of Computing Systems, Volume 43, Issue 2

Pages 118 - 135

https://doi.org/10.1007/s00224-007-9023-8

Published: 07 April 2008 Publication History

Abstract

Disjoint $\mathsf{NP}$-pairs are a well studied complexity-theoretic concept with important applications in cryptography and propositional proof complexity. In this paper we introduce a natural generalization of the notion of disjoint $\mathsf{NP}$-pairs to disjoint k-tuples of $\mathsf{NP}$-sets for k≥2. We define subclasses of the class of all disjoint k-tuples of $\mathsf{NP}$-sets. These subclasses are associated with a propositional proof system and possess complete tuples which are defined from the proof system.

In our main result we show that complete disjoint $\mathsf{NP}$-pairs exist if and only if complete disjoint k-tuples of $\mathsf{NP}$-sets exist for all k≥2. Further, this is equivalent to the existence of a propositional proof system in which the disjointness of all k-tuples is shortly provable. We also show that a strengthening of this conditions characterizes the existence of optimal proof systems.

Cited By

View all

Beyersdorff OSadowski Z(2011)Do there exist complete sets for promise classes?Mathematical Logic Quarterly10.1002/malq.20101002157:6(535-550)Online publication date: 16-Jun-2011
Beyersdorff OKöbler JMessner J(2009)Nondeterministic functions and the existence of optimal proof systemsTheoretical Computer Science10.1016/j.tcs.2009.05.021410:38-40(3839-3855)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.05.021
Beyersdorff O(2007)The deduction theorem for strong propositional proof systemsProceedings of the 27th international conference on Foundations of software technology and theoretical computer science10.5555/1781794.1781816(241-252)Online publication date: 12-Dec-2007
https://dl.acm.org/doi/10.5555/1781794.1781816

Index Terms

Tuples of Disjoint $\mathsf{NP}$-Sets
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Theorem proving algorithms
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Logic
    1. Proof theory

Recommendations

Tuples of disjoint NP-sets
CSR'06: Proceedings of the First international computer science conference on Theory and Applications

Disjoint NP-pairs are a well studied complexity theoretic concept with important applications in cryptography and propositional proof complexity. In this paper we introduce a natural generalization of the notion of disjoint NP-pairs to disjoint k-tuples ...
Canonical disjoint NP-pairs of propositional proof systems

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is identical. ...
Splitting NP-Complete Sets

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long-standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glaßer et al., complete sets for all of the following ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Theory of Computing Systems Volume 43, Issue 2

April 2008

195 pages

ISSN:1432-4350

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 April 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Beyersdorff OSadowski Z(2011)Do there exist complete sets for promise classes?Mathematical Logic Quarterly10.1002/malq.20101002157:6(535-550)Online publication date: 16-Jun-2011
Beyersdorff OKöbler JMessner J(2009)Nondeterministic functions and the existence of optimal proof systemsTheoretical Computer Science10.1016/j.tcs.2009.05.021410:38-40(3839-3855)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.05.021
Beyersdorff O(2007)The deduction theorem for strong propositional proof systemsProceedings of the 27th international conference on Foundations of software technology and theoretical computer science10.5555/1781794.1781816(241-252)Online publication date: 12-Dec-2007
https://dl.acm.org/doi/10.5555/1781794.1781816

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Tuples of disjoint NP-sets

Canonical disjoint NP-pairs of propositional proof systems

Splitting NP-Complete Sets

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations