Autoreducibility of NP-complete sets under strong hypotheses
type: Item
instance of: scholarly article
title: Autoreducibility of NP-complete sets under strong hypotheses
zbMATH Open document ID: 1390.68321
author: John M. Hitchcock
author: Hadi Shafei
published in: Computational Complexity
publication date: 2018-04-18T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 6861523
zbMATH Keywords: NP-completeness
zbMATH Keywords: autoreducibility
zbMATH Keywords: genericity
MaRDI profile type: Publication
full work available at URL: s00037-017-0157-z
OpenAlex ID: W2739273244
cites work: Q3337457
cites work: Separating NP-completeness notions under strong hypotheses
cites work: Diagonalizations over polynomial time computable sets
cites work: On being incoherent without being very hard
cites work: Separating Complexity Classes Using Autoreducibility
cites work: Non-uniform reductions
cites work: Q3396548
cites work: Autoreducibility, mitoticity, and immunity
cites work: Comparing reductions to NP-complete sets
cites work: Hardness hypotheses, derandomization, and circuit complexity
cites work: A comparison of polynomial time reducibilities
cites work: Cook versus Karp-Levin: Separating completeness notions if NP is not small
cites work: Q2965519
cites work: Bi-immunity separates strong NP-completeness notions
cites work: Q5619818
DOI: 10.1007/S00037-017-0157-Z
description: scientific article; zbMATH DE number 6861523