On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
type: Item
instance of: scholarly article
title: On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
zbMATH Open document ID: 1261.03158
author: Edward A. Hirsch
author: Dmitry Itsykson
author: Ivan Monakhov
author: Alexander V. Smal
published in: Theory of Computing Systems
publication date: 2012-12-07T00:00:00Z
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03B05
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 6113700
zbMATH Keywords: propositional proof complexity
zbMATH Keywords: optimal algorithm
zbMATH Keywords: infinitely-often one-way
zbMATH Keywords: heuristic algorithm
zbMATH Keywords: heuristic acceptor
zbMATH Keywords: recursively enumerable languages
MaRDI profile type: Publication
full work available at URL: s00224-011-9354-3
OpenAlex ID: W1995485918
cites work: Pseudorandom Generators in Propositional Proof Complexity
cites work: Average-Case Complexity
cites work: Consequences of the provability of NP ⊆ P/poly
cites work: The relative efficiency of propositional proof systems
cites work: A Complete Public-Key Cryptosystem
cites work: An infinitely-often one-way function based on an average-case assumption
cites work: A Pseudorandom Generator from any One-way Function
cites work: On Robust Combiners for Oblivious Transfer and Other Primitives
cites work: Structural complexity of AvgBPP
cites work: Propositional proof systems, the consistency of first order theories and the complexity of computations
cites work: On the weak pigeonhole principle
cites work: Tautologies from pseudo-random generators
cites work: One way functions and pseudorandom generators
cites work: Q4226453
cites work: Q4251070
cites work: Speedup for natural problems and noncomputability
cites work: On reducibility and symmetry of disjoint NP pairs.
cites work: Q4263798
DOI: 10.1007/S00224-011-9354-3
description: scientific article; zbMATH DE number 6113700