Collapsing and separating completeness notions under average-case and worst-case hypotheses
type: Item
instance of: scholarly article
title: Collapsing and separating completeness notions under average-case and worst-case hypotheses
zbMATH Open document ID: 1253.68150
author: Xiaoyang Gu
author: John M. Hitchcock
author: Aduri Pavan
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/2462/
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6113697
zbMATH Keywords: computational complexity
zbMATH Keywords: NP-completeness
zbMATH Keywords: Turing completeness
zbMATH Keywords: length-increasing reductions
zbMATH Keywords: approximable sets
MaRDI profile type: Publication
OpenAlex ID: W1568724636
cites work: Computational Complexity
cites work: Some connections between bounded query classes and non-uniform complexity.
cites work: Separating NP-completeness notions under strong hypotheses
cites work: Q4131649
cites work: On being incoherent without being very hard
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: Non-uniform reductions
cites work: Completeness for nondeterministic complexity classes
cites work: The complexity of theorem-proving procedures
cites work: On coherence, random-self-reducibility, and self-correction
cites work: The power of adaptiveness and additional queries in random-self- reductions
cites work: Q3549693
cites work: Complete Problems and Strong Polynomial Reducibilities
cites work: On Constructing 1-1 One-Way Functions
cites work: \(p\)-Selective sets and reducing search to decision vs. self-reducibility
cites work: Comparing reductions to NP-complete sets
cites work: Partial bi-immunity, scaled dimension, and NP-completeness
cites work: Q4252738
cites work: Q4526985
cites work: Q3285920
cites work: A comparison of polynomial time reducibilities
cites work: Measure, Stochasticity, and the Density of Hard Languages
cites work: Cook versus Karp-Levin: Separating completeness notions if NP is not small
cites work: Hardness vs randomness
cites work: Separation of NP-completeness notions
cites work: Bi-immunity separates strong NP-completeness notions
cites work: Pseudorandom generators without the XOR lemma
cites work: A comparison of polynomial time completeness notions
DOI: 10.1007/S00224-011-9365-0
Recommended article: Q3113769
Recommended article: Q3805899
Recommended article: Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis
Recommended article: Reductions, completeness and the hardness of approximability
Recommended article: Q3217603
Recommended article: Q4218123
Recommended article: Average-case intractability vs. worst-case intractability
Recommended article: On the Average Case Complexity of Some P-complete Problems
Recommended article: Complete on average Boolean satisfiability
Recommended article: Worst-case expansions of complete theories
description: scientific article; zbMATH DE number 6113697