A remark on pseudo proof systems and hard instances of the satisfiability problem

DOI10.1002/malq.201700009OpenAlexW2900953594MaRDI QIDQ5109236

Jan Malý, Moritz Müller

Publication date: 11 May 2020

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.201700009

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Related Items (2)

Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds

Cites Work

• A note on SAT algorithms and proof complexity
• Circuit lower bounds in bounded arithmetics
• Construction of models of bounded arithmetic by restricted reduced powers
• On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography
• Models of arithmetic and recursive functions
• Randomizing a model
• Encoding invariance in average case complexity
• Sub-arithmetical ultrapowers: A survey
• If NP languages are hard on the worst-case, then it is easy to find their hard instances
• Simple strategies for large zero-sum games with applications to complexity theory
• ON OPTIMAL INVERTERS
• The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• The relative efficiency of propositional proof systems
• Boolean ultrapowers
• Improving on Gutfreund, Shaltiel,and Ta-Shma’s Paper “If NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances”
• Randomness, pseudorandomness and models of arithmetic
• Computational Complexity
• A proof of the independence of the continuum hypothesis
• The theory of Boolean ultrapowers
• Algebraic treatment of the notion of satisfiability
• Hard Instances of Algorithms and Proof Systems
• Easiness assumptions and hardness tests: Trading time for zero error
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A remark on pseudo proof systems and hard instances of the satisfiability problem