Bi-immunity separates strong NP-completeness notions
type: Item
instance of: scholarly article
title: Bi-immunity separates strong NP-completeness notions
zbMATH Open document ID: 1078.68042
author: Aduri Pavan
author: Alan L. Selman
published in: Information and Computation
publication date: 2004-11-23T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 2118428
zbMATH Keywords: Turing completeness
zbMATH Keywords: Many-one completeness
zbMATH Keywords: Bi-immunity
MaRDI profile type: Publication
full work available at URL: j.ic.2003.05.001
OpenAlex ID: W1964450092
cites work: Separating NP-completeness notions under strong hypotheses
cites work: Resource bounded randomness and weakly complete problems
cites work: Q3996675
cites work: Bi-immune sets for complexity classes
cites work: Lower Bounds for Selection in X + Y and Other Multisets
cites work: A comparison of polynomial time reducibilities
cites work: Cook versus Karp-Levin: Separating completeness notions if NP is not small
cites work: Cook reducibility is faster than Karp reducibility in NP
cites work: Separation of NP-completeness notions
cites work: Reductions on NP and p-selective sets
DOI: 10.1016/J.IC.2003.05.001
description: scientific article; zbMATH DE number 2118428