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

DOI10.1007/S00224-011-9354-3MaRDI QIDQ693058zbMATH OpenOpenAlexFDO

Authors Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, 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 algorithmpropositional proof complexityrecursively enumerable languagesheuristic acceptorinfinitely-often one-way

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5999718
• scientific article; zbMATH DE number 1304339
• Optimal acceptors and optimal proof systems
• Optimal proof systems imply complete sets for promise classes
• scientific article; zbMATH DE number 2019634

Cites work

• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1304339 (Why is no real title available?)
• scientific article; zbMATH DE number 1342213 (Why is no real title available?)
• A Complete Public-Key Cryptosystem
• A Pseudorandom Generator from any One-way Function
• An infinitely-often one-way function based on an average-case assumption
• Average-Case Complexity
• Consequences of the provability of NP ⊆ P/poly
• On Robust Combiners for Oblivious Transfer and Other Primitives
• On reducibility and symmetry of disjoint NP pairs.
• On the weak pigeonhole principle
• One way functions and pseudorandom generators
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Pseudorandom Generators in Propositional Proof Complexity
• Speedup for natural problems and noncomputability
• Structural complexity of AvgBPP
• Tautologies from pseudo-random generators
• The relative efficiency of propositional proof systems

Cited in

(6)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693058)