In search of an easy witness: Exponential time vs. probabilistic polynomial time.
type: Item
instance of: scholarly article
title: In search of an easy witness: Exponential time vs. probabilistic polynomial time.
zbMATH Open document ID: 1059.68047
DOI: 10.1016/S0022-0000(02)00024-7
author: Russell Impagliazzo
author: Valentine Kabanets
author: A. Wigderson
published in: Journal of Computer and System Sciences
publication date: 2003-05-14T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1910856
zbMATH Keywords: search space
MaRDI profile type: Publication
cites work: A new general derandomization method
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: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
cites work: Q4783716
cites work: Q4258566
cites work: Q4256650
cites work: Modern cryptography, probabilistic proofs and pseudo-randomness
cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME
cites work: Q4526985
cites work: Easiness assumptions and hardness tests: Trading time for zero error
cites work: Q3152808
cites work: Turing machines that take advice
cites work: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
cites work: Derandomizing Arthur-Merlin games under uniform assumptions
cites work: Derandomizing Arthur-Merlin games using hitting sets
cites work: Hardness vs randomness
cites work: Q3221403
cites work: Natural proofs
cites work: Pseudorandom generators without the XOR lemma (extended abstract)
full work available at URL: s0022-0000(02)00024-7
OpenAlex ID: W2158747250
description: scientific article; zbMATH DE number 1910856