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

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