Avoiding simplicity is complex
type: Item
instance of: scholarly article
title: Avoiding simplicity is complex
zbMATH Open document ID: 1253.68186
author: Holger Spakowski
author: Eric Allender
published in: Theory of Computing Systems
publication date: 2012-12-07T00:00:00Z
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6113709
zbMATH Keywords: hitting sets
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: complexity theory
zbMATH Keywords: \(\mathrm{Kt}\) complexity
zbMATH Keywords: \(\mathrm{KNt}\) complexity
MaRDI profile type: Publication
full work available at URL: s00224-011-9334-7
OpenAlex ID: W2042851910
cites work: Some consequences of the existnce of pseudorandom generators
cites work: Q4474202
cites work: Avoiding Simplicity Is Complex
cites work: Power from Random Strings
cites work: The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
cites work: Computational Complexity
cites work: Non-deterministic exponential time has two-prover interactive protocols
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: Resource-bounded Kolmogorov complexity revisited
cites work: Unconditional Lower Bounds against Advice
cites work: Separating NE from Some Nonuniform Nondeterministic Complexity Classes
cites work: Polynomial-time compression
cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME
cites work: A Pseudorandom Generator from any One-way Function
cites work: In search of an easy witness: Exponential time vs. probabilistic polynomial time.
cites work: Q4526985
cites work: Randomness conservation inequalities; information and independence in mathematical theories
cites work: Algebraic methods for interactive proof systems
cites work: Separating Nondeterministic Time Complexity Classes
cites work: IP = PSPACE
DOI: 10.1007/S00224-011-9334-7
description: scientific article; zbMATH DE number 6113709