{"data":{"id":"10.48550/arxiv.cond-mat/0601703","type":"dois","attributes":{"doi":"10.48550/arxiv.cond-mat/0601703","prefix":"10.48550","suffix":"arxiv.cond-mat/0601703","identifiers":[{"identifier":"cond-mat/0601703","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"cond-mat/0601703"}],"creators":[{"name":"Ardelius, John","nameType":"Personal","givenName":"John","familyName":"Ardelius","affiliation":[],"nameIdentifiers":[]},{"name":"Aurell, Erik","nameType":"Personal","givenName":"Erik","familyName":"Aurell","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Behavior of heuristics and state space structure near SAT/UNSAT transition"}],"publisher":"arXiv","container":{},"publicationYear":2006,"subjects":[{"lang":"en","subject":"Statistical Mechanics (cond-mat.stat-mech)","subjectScheme":"arXiv"},{"subject":"FOS: Physical sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Physical sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2006-01-31T14:02:14Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2013-05-29T15:56:01Z","dateType":"Updated","dateInformation":"v1"},{"date":"2006-01","dateType":"Available","dateInformation":"v1"},{"date":"2006","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1103/physreve.74.037702","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"1","rightsList":[{"rights":"Assumed arXiv.org perpetual, non-exclusive license to distribute this article for submissions made before January 2004","rightsUri":"http://arxiv.org/licenses/assumed-1991-2003/"}],"descriptions":[{"description":"We study the behavior of ASAT, a heuristic for solving satisfiability problems by stochastic local search near the SAT/UNSAT transition. The heuristic is focused, i.e. only variables in unsatisfied clauses are updated in each step, and is significantly simpler, while similar to, walksat or Focused Metropolis Search. We show that ASAT solves instances as large as one million variables in linear time, on average, up to 4.21 clauses per variable for random 3SAT. For K higher than 3, ASAT appears to solve instances at the ``FRSB threshold'' in linear time, up to K=7.","descriptionType":"Abstract"},{"description":"12 pages, 6 figures, longer version available as MSc thesis of first author at http://biophys.physics.kth.se/docs/ardelius_thesis.pdf","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi5DT05ELU1BVC8wNjAxNzAzPC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+Y29uZC1tYXQvMDYwMTcwMzwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5BcmRlbGl1cywgSm9objwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+Sm9objwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5BcmRlbGl1czwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5BdXJlbGwsIEVyaWs8L2NyZWF0b3JOYW1lPgogICAgICA8Z2l2ZW5OYW1lPkVyaWs8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+QXVyZWxsPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogIDwvY3JlYXRvcnM+CiAgPHRpdGxlcz4KICAgIDx0aXRsZT5CZWhhdmlvciBvZiBoZXVyaXN0aWNzIGFuZCBzdGF0ZSBzcGFjZSBzdHJ1Y3R1cmUgbmVhciBTQVQvVU5TQVQgdHJhbnNpdGlvbjwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPHB1Ymxpc2hlcj5hclhpdjwvcHVibGlzaGVyPgogIDxwdWJsaWNhdGlvblllYXI+MjAwNjwvcHVibGljYXRpb25ZZWFyPgogIDxzdWJqZWN0cz4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPlN0YXRpc3RpY2FsIE1lY2hhbmljcyAoY29uZC1tYXQuc3RhdC1tZWNoKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IFBoeXNpY2FsIHNjaWVuY2VzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAwNi0wMS0zMVQxNDowMjoxNFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxMy0wNS0yOVQxNTo1NjowMVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iQXZhaWxhYmxlIiBkYXRlSW5mb3JtYXRpb249InYxIj4yMDA2LTAxPC9kYXRlPgogIDwvZGF0ZXM+CiAgPHJlc291cmNlVHlwZSByZXNvdXJjZVR5cGVHZW5lcmFsPSJUZXh0Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHJlbGF0ZWRJZGVudGlmaWVycz4KICAgIDxyZWxhdGVkSWRlbnRpZmllciByZWxhdGVkSWRlbnRpZmllclR5cGU9IkRPSSIgcmVsYXRpb25UeXBlPSJJc1ZlcnNpb25PZiI+MTAuMTEwMy9QaHlzUmV2RS43NC4wMzc3MDI8L3JlbGF0ZWRJZGVudGlmaWVyPgogIDwvcmVsYXRlZElkZW50aWZpZXJzPgogIDx2ZXJzaW9uPjE8L3ZlcnNpb24+CiAgPHJpZ2h0c0xpc3Q+CiAgICA8cmlnaHRzIHJpZ2h0c1VSST0iaHR0cDovL2FyeGl2Lm9yZy9saWNlbnNlcy9hc3N1bWVkLTE5OTEtMjAwMy8iPkFzc3VtZWQgYXJYaXYub3JnIHBlcnBldHVhbCwgbm9uLWV4Y2x1c2l2ZSBsaWNlbnNlIHRvIGRpc3RyaWJ1dGUgdGhpcyBhcnRpY2xlIGZvciBzdWJtaXNzaW9ucyBtYWRlIGJlZm9yZSBKYW51YXJ5IDIwMDQ8L3JpZ2h0cz4KICA8L3JpZ2h0c0xpc3Q+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij5XZSBzdHVkeSB0aGUgYmVoYXZpb3Igb2YgQVNBVCwgYSBoZXVyaXN0aWMgZm9yIHNvbHZpbmcgc2F0aXNmaWFiaWxpdHkgcHJvYmxlbXMgYnkgc3RvY2hhc3RpYyBsb2NhbCBzZWFyY2ggbmVhciB0aGUgU0FUL1VOU0FUIHRyYW5zaXRpb24uIFRoZSBoZXVyaXN0aWMgaXMgZm9jdXNlZCwgaS5lLiBvbmx5IHZhcmlhYmxlcyBpbiB1bnNhdGlzZmllZCBjbGF1c2VzIGFyZSB1cGRhdGVkIGluIGVhY2ggc3RlcCwgYW5kIGlzIHNpZ25pZmljYW50bHkgc2ltcGxlciwgd2hpbGUgc2ltaWxhciB0bywgd2Fsa3NhdCBvciBGb2N1c2VkIE1ldHJvcG9saXMgU2VhcmNoLiBXZSBzaG93IHRoYXQgQVNBVCBzb2x2ZXMgaW5zdGFuY2VzIGFzIGxhcmdlIGFzIG9uZSBtaWxsaW9uIHZhcmlhYmxlcyBpbiBsaW5lYXIgdGltZSwgb24gYXZlcmFnZSwgdXAgdG8gNC4yMSBjbGF1c2VzIHBlciB2YXJpYWJsZSBmb3IgcmFuZG9tIDNTQVQuIEZvciBLIGhpZ2hlciB0aGFuIDMsIEFTQVQgYXBwZWFycyB0byBzb2x2ZSBpbnN0YW5jZXMgYXQgdGhlIGBgRlJTQiB0aHJlc2hvbGQnJyBpbiBsaW5lYXIgdGltZSwgdXAgdG8gSz03LjwvZGVzY3JpcHRpb24+CiAgICA8ZGVzY3JpcHRpb24gZGVzY3JpcHRpb25UeXBlPSJPdGhlciI+MTIgcGFnZXMsIDYgZmlndXJlcywgbG9uZ2VyIHZlcnNpb24gYXZhaWxhYmxlIGFzIE1TYyB0aGVzaXMgb2YgZmlyc3QgYXV0aG9yIGF0IGh0dHA6Ly9iaW9waHlzLnBoeXNpY3Mua3RoLnNlL2RvY3MvYXJkZWxpdXNfdGhlc2lzLnBkZjwvZGVzY3JpcHRpb24+CiAgPC9kZXNjcmlwdGlvbnM+CjwvcmVzb3VyY2U+","url":"https://arxiv.org/abs/cond-mat/0601703","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-17T21:28:51.000Z","registered":"2022-03-17T21:28:52.000Z","published":"2006","updated":"2022-03-17T21:28:52.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.cond-mat/0601703","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}