2026-04-17T02:52:37Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/1264702026-01-24T06:10:52Zcom_2072_1033col_2072_452950

A remark on pseudo proof systems and hard instances of the satisfiability problem Maly, Jan Muller, Moritz Martin Àrees temàtiques de la UPC::Informàtica Satisfiability Problem (SAT) We link two concepts from the literature, namely hard sequences for the satisfiability problem sat and so-called pseudo proof systems proposed for study by Krajícek. Pseudo proof systems are elements of a particular nonstandard model constructed by forcing with random variables. We show that the existence of mad pseudo proof systems is equivalent to the existence of a randomized polynomial time procedure with a highly restrictive use of randomness which produces satisfiable formulas whose satisfying assignments are probably hard to find. Peer Reviewed Postprint (published version) 2018-11-20 Article https://onlinelibrary.wiley.com/doi/10.1002/malq.201700009 info:eu-repo/grantAgreement/EC/H2020/648276/EU/A Unified Theory of Algorithmic Relaxations/AUTAR http://creativecommons.org/licenses/by/3.0/es/ Open Access Attribution 3.0 Spain