On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
From MaRDI portal
Publication:693058
DOI10.1007/s00224-011-9354-3zbMath1261.03158MaRDI 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
heuristic algorithm; optimal algorithm; recursively enumerable languages; propositional proof complexity; heuristic acceptor; infinitely-often one-way
94A60: Cryptography
03D15: Complexity of computation (including implicit computational complexity)
03B05: Classical propositional logic
68W20: Randomized algorithms
03F20: Complexity of proofs
Related Items
A remark on pseudo proof systems and hard instances of the satisfiability problem, Towards NP-P via proof complexity and search, On an optimal randomized acceptor for graph nonisomorphism, 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