Inseparability and strong hypotheses for disjoint NP pairs
type: Item
instance of: scholarly article
title: Inseparability and strong hypotheses for disjoint NP pairs
zbMATH Open document ID: 1282.68113
author: Jack H. Lutz
author: Elvira Mayordomo
author: Lance Fortnow
published in: Theory of Computing Systems
publication date: 2012-12-07T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2471/
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6113702
zbMATH Keywords: computational complexity
zbMATH Keywords: disjoint NP-pairs
zbMATH Keywords: resource-bounded measure
zbMATH Keywords: genericity
Wikidata QID: Q60578957
MaRDI profile type: Publication
OpenAlex ID: W2011854900
cites work: Diagonalizations over polynomial time computable sets
cites work: Q4348122
cites work: Resource bounded randomness and weakly complete problems
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Equivalence of Measures of Complexity Classes
cites work: The relative efficiency of propositional proof systems
cites work: The complexity of promise problems with applications to public-key cryptography
cites work: Separability and one-way functions
cites work: Reductions between disjoint NP-pairs
cites work: Disjoint NP-Pairs
cites work: Canonical disjoint NP-pairs of propositional proof systems
cites work: The Informational Content of Canonical Disjoint NP-Pairs
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: Oracles for structural properties: The isomorphism problem and public-key cryptography
cites work: Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
cites work: Relative to a random oracle, NP is not small
cites work: Genericity and randomness over feasible probability measures
cites work: Almost everywhere high nonuniform complexity
cites work: Q4359463
cites work: Q4790382
DBLP publication ID: journals/mst/FortnowLM12
DOI: 10.1007/S00224-011-9326-7
Recommended article: Inseparability and Strong Hypotheses for Disjoint NP Pairs.
Recommended article: Separating NP-completeness notions under strong hypotheses
Recommended article: Q3436752
Recommended article: NP-Completeness, Proof Systems, and Disjoint NP-Pairs.
Recommended article: Theory and Applications of Models of Computation
Recommended article: Proof system representations of degrees of disjoint NP-pairs
Recommended article: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Recommended article: Disjoint NP-Pairs
Recommended article: THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
Recommended article: The Informational Content of Canonical Disjoint NP-Pairs
description: scientific article; zbMATH DE number 6113702