Almost every set in exponential time is P-bi-immune
type: Item
instance of: scholarly article
title: Almost every set in exponential time is P-bi-immune
zbMATH Open document ID: 0874.68161
DOI: 10.1016/0304-3975(94)00023-C
author: Elvira Mayordomo
published in: Theoretical Computer Science
publication date: 1997-02-27T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 983740
Wikidata QID: Q60578990
MaRDI profile type: Publication
cites work: Diagonalizations over polynomial time computable sets
cites work: Bi-immune sets for complexity classes
cites work: Q4035688
cites work: Q4769049
cites work: Relativizations comparing NP and exponential time
cites work: A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: On 1-truth-table-hard languages
cites work: Completeness, Approximation and Density
cites work: Category and Measure in Complexity Classes
cites work: Almost everywhere high nonuniform complexity
cites work: On Reducibility to Complex or Sparse Sets
cites work: Q5620774
cites work: Recursively enumerable sets of positive integers and their decision problems
cites work: Provably Difficult Combinatorial Games
DBLP publication ID: journals/tcs/Mayordomo94
description: scientific article; zbMATH DE number 983740