On resource-bounded instance complexity
type: Item
instance of: scholarly article
title: On resource-bounded instance complexity
zbMATH Open document ID: 0872.68044
DOI: 10.1016/0304-3975(95)00097-6
author: Martin Kummer
author: Lance Fortnow
published in: Theoretical Computer Science
publication date: 1997-02-27T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 984571
MaRDI profile type: Publication
full work available at URL: 0304-3975(95)00097-6
OpenAlex ID: W1966098169
cites work: Polynomial terse sets
cites work: Q4039803
cites work: Q3996675
cites work: Random strings make hard instances
cites work: Q4281495
cites work: On sparse sets in NP-P
cites work: On reductions of NP sets to sparse sets
cites work: On the notion of infinite pseudorandom sequences
cites work: Q4727431
cites work: Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
cites work: Q4023358
cites work: Almost every set in exponential time is P-bi-immune
cites work: Instance complexity
cites work: Q3221403
cites work: P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
cites work: On one-one polynomial time equivalence relations
description: scientific article; zbMATH DE number 984571