{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T03:51:37Z","timestamp":1649130697085},"reference-count":0,"publisher":"IOS Press","license":[{"start":{"date-parts":[[2021,10,29]],"date-time":"2021-10-29T00:00:00Z","timestamp":1635465600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,10,29]]},"abstract":"<jats:p>The results of a computational experiment on the assessment of the complexity of proving the unsatisfiability of random 3-CNF logical formulas are presented. The dependence of the complexity of this proving on the R-ratio of the number of clauses to the number of variables is demonstrated. The computational experiment was carried out for the range of the N-number of variables from 256 to 512. An exponential dependence of the median complexity of proving the unsatisfiability of formulas on the number of variables was revealed for each of R value: 4.3, 4.6, 5.0, 5.5, 6.0. A formula is constructed that approximates the results of the experiment. According to this formula the exponential component of the median complexity of the analysis of random 3-CNF is estimated as 2 to the power N \/ (8.4R-17.8).<\/jats:p>","DOI":"10.3233\/faia210281","type":"book-chapter","created":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T19:25:45Z","timestamp":1635881145000},"source":"Crossref","is-referenced-by-count":0,"title":["About Strong Dependence of the Complexity of Analysis of the Random 3-CNF Formulas on the Ratio of Number of Clauses to the Number of Variables"],"prefix":"10.3233","author":[{"given":"Sergey I.","family":"Uvarov","sequence":"first","affiliation":[{"name":"Institute of control Science RAS, Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","Modern Management based on Big Data II and Machine Learning and Intelligent Systems III"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA210281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T19:25:47Z","timestamp":1635881147000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA210281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,29]]},"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia210281","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"value":"0922-6389","type":"print"},{"value":"1879-8314","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,29]]}}}