Tuples of disjoint \(\mathsf{NP}\)-sets
type: Item
instance of: scholarly article
title: Tuples of disjoint \(\mathsf{NP}\)-sets
zbMATH Open document ID: 1148.68021
author: Olaf Beyersdorff
published in: Theory of Computing Systems
publication date: 2008-06-17T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 5288687
zbMATH Keywords: Propositional proof systems
MaRDI profile type: Publication
full work available at URL: s00224-007-9023-8
OpenAlex ID: W1999473833
Wikidata QID: Q59903789
cites work: Classes of representable disjoint \textsf{NP}-pairs
cites work: Q3794177
cites work: The relative efficiency of propositional proof systems
cites work: Disjoint NP-Pairs
cites work: Reductions between disjoint NP-pairs
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: Optimal proof systems imply complete sets for promise classes
cites work: Q4856172
cites work: Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
cites work: Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
cites work: Propositional proof systems, the consistency of first order theories and the complexity of computations
cites work: Quantified propositional calculi and fragments of bounded arithmetic
cites work: Some consequences of cryptographical conjectures for \(S_2^1\) and EF
cites work: On the Structure of Polynomial Time Reducibility
cites work: On reducibility and symmetry of disjoint NP pairs.
DBLP publication ID: journals/mst/Beyersdorff08
DOI: 10.1007/S00224-007-9023-8
Recommended article: Tuples of Disjoint NP-Sets
Recommended article: Unions of Disjoint NP-Complete Sets
Recommended article: Disjoint NP-Pairs
Recommended article: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Recommended article: Classes of representable disjoint \textsf{NP}-pairs
Recommended article: The complexity of unions of disjoint sets
Recommended article: The Complexity of Unions of Disjoint Sets
Recommended article: NP-Completeness, Proof Systems, and Disjoint NP-Pairs.
Recommended article: Q3680278
description: scientific article; zbMATH DE number 5288687