{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T12:03:57Z","timestamp":1759147437815,"version":"3.40.5"},"reference-count":38,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T00:00:00Z","timestamp":1542672000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC\u20102014\u2010CoG 648276"],"award-info":[{"award-number":["ERC\u20102014\u2010CoG 648276"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P25207","P28699","Y698"],"award-info":[{"award-number":["P25207","P28699","Y698"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We link two concepts from the literature, namely hard sequences for the satisfiability problem <jats:sc>sat<\/jats:sc> and so\u2010called pseudo proof systems proposed for study by Kraj\u00ed\u010dek. Pseudo proof systems are elements of a particular nonstandard model constructed by forcing with random variables. We show that the existence of <jats:italic>mad<\/jats:italic>\npseudo 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.<\/jats:p>","DOI":"10.1002\/malq.201700009","type":"journal-article","created":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T13:56:47Z","timestamp":1542722207000},"page":"418-428","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A remark on pseudo proof systems and hard instances of the satisfiability problem"],"prefix":"10.1002","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3288-7462","authenticated-orcid":false,"given":"Jan","family":"Maly","sequence":"first","affiliation":[{"name":"Institute of Logic and Computation Technische Universit\u00e4t Wien Favoritenstra\u00dfe 9 1040 Wien Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moritz","family":"M\u00fcller","sequence":"additional","affiliation":[{"name":"Kurt G\u00f6del Research Center University of Vienna W\u00e4hringer Stra\u00dfe 25 1090 Wien Austria"},{"name":"Computer Science Department Universitat Polit\u00e8cnica de Catalunya Omega\u2013327, Campus Nord, c\/ Jordi Girona 1\u20103 08034 Barcelona Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2018,11,20]]},"reference":[{"key":"e_1_2_6_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_6_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.17"},{"key":"e_1_2_6_4_1","first-page":"290","volume-title":"Innovations in Computer Science, ICS 2010, Tsinghua University, Beijing, China","author":"Bogdanov A.","year":"2010"},{"key":"e_1_2_6_5_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000004"},{"key":"e_1_2_6_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1755-2567.1997.tb00745.x"},{"key":"e_1_2_6_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688115"},{"key":"e_1_2_6_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/bsl.2013.2"},{"key":"e_1_2_6_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601336"},{"key":"e_1_2_6_10_1","first-page":"83","volume-title":"Proceedings of the 7th Annual ACM Symposium on Theory of Computing, May 5\u20137, 1975, Albuquerque, New Mexico, USA","author":"Cook A.","year":"1975"},{"key":"e_1_2_6_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/035\/01"},{"key":"e_1_2_6_12_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_2_6_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-016-0484-9"},{"key":"e_1_2_6_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0235-8"},{"volume-title":"Metamathematics of First\u2010Order Arithmetic","year":"1998","author":"H\u00e1jek P.","key":"e_1_2_6_15_1"},{"key":"e_1_2_6_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9354-3"},{"key":"e_1_2_6_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02757881"},{"volume-title":"Set Theory, The Third Millenium Edition, Revised and Expanded","year":"2002","author":"Jech T.","key":"e_1_2_6_18_1"},{"key":"e_1_2_6_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1763"},{"volume-title":"Foundations of Infinitesimal Calculus","year":"1976","author":"Keisler J.","key":"e_1_2_6_20_1"},{"key":"e_1_2_6_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1998.1793"},{"key":"e_1_2_6_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"e_1_2_6_23_1","first-page":"104","volume-title":"Logic Colloquium '95, Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic","author":"Kraj\u00ed\u010dek J.","year":"1998"},{"volume-title":"Forcing with Random variables and Proof Complexity","year":"2011","author":"Kraj\u00ed\u010dek J.","key":"e_1_2_6_24_1"},{"key":"e_1_2_6_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.03.009"},{"key":"e_1_2_6_26_1","first-page":"277","volume-title":"Logic and Algorithmic, Proceedings of An International Symposium Held in Honor of Ernst Specker in Z\u00fcrich","author":"Kripke S.","year":"1982"},{"issue":"3","key":"e_1_2_6_27_1","first-page":"265","article-title":"Universal sequential search problems","volume":"9","author":"Levin L.","year":"1973","journal-title":"Probl. Inf. Transm."},{"key":"e_1_2_6_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195447"},{"key":"e_1_2_6_29_1","unstructured":"J.Maly Jan Kraj\u00ed\u010dek's Forcing Construction and Pseudo Proof Systems Master's thesis (Universit\u00e4t Wien 2016)."},{"key":"e_1_2_6_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(71)90017-9"},{"key":"e_1_2_6_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90064-9"},{"key":"e_1_2_6_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2014.08.004"},{"key":"e_1_2_6_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02025117"},{"key":"e_1_2_6_34_1","first-page":"199","volume-title":"New Studies in Weak Arithmetics","author":"Pudl\u00e1k P.","year":"2013"},{"key":"e_1_2_6_35_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-40-1-62-95"},{"key":"e_1_2_6_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01705520"},{"key":"e_1_2_6_37_1","unstructured":"L.Stockmeyer The Complexity of Decision Problems in Automata Theory Ph.D. thesis (Massachusetts Institute of Technology 1974)."},{"key":"e_1_2_6_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38536-0_18"},{"key":"e_1_2_6_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9517-5"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.201700009","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.201700009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T00:54:39Z","timestamp":1694739279000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.201700009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,20]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1002\/malq.201700009"],"URL":"https:\/\/doi.org\/10.1002\/malq.201700009","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[2018,11,20]]},"assertion":[{"value":"2017-03-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-17","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}