On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography

DOI10.1007/s00224-011-9354-3zbMath1261.03158OpenAlexW1995485918MaRDI QIDQ693058

Ivan Monakhov, Edward A. Hirsch, Dmitry Itsykson, Alexander V. Smal

Publication date: 7 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9354-3

zbMATH Keywords

heuristic algorithmoptimal algorithmrecursively enumerable languagespropositional proof complexityheuristic acceptorinfinitely-often one-way

Mathematics Subject Classification ID

Cryptography (94A60) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Randomized algorithms (68W20) Complexity of proofs (03F20)

Related Items (4)

Towards NP-P via proof complexity and search ⋮ On an optimal randomized acceptor for graph nonisomorphism ⋮ A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Optimal heuristic algorithms for the image of an injective function

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Speedup for natural problems and noncomputability
• Structural complexity of AvgBPP
• One way functions and pseudorandom generators
• On reducibility and symmetry of disjoint NP pairs.
• Tautologies from Pseudo-Random Generators
• On the weak pigeonhole principle
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Average-Case Complexity
• An infinitely-often one-way function based on an average-case assumption
• A Complete Public-Key Cryptosystem
• The relative efficiency of propositional proof systems
• A Pseudorandom Generator from any One-way Function
• Pseudorandom Generators in Propositional Proof Complexity
• On Robust Combiners for Oblivious Transfer and Other Primitives
• Consequences of the provability of NP ⊆ P/poly

This page was built for publication: On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography