{"entities":{"Q1114394":{"pageid":1125143,"ns":120,"title":"Item:Q1114394","lastrevid":49238314,"modified":"2026-01-06T20:11:25Z","type":"item","id":"Q1114394","labels":{"en":{"language":"en","value":"Polynomially solvable satisfiability problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4082968"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114394$E12ECA82-4177-4700-A4EB-97D5B4DCCDDB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0bb18f91f29766b3f4da9f49ac48cd3c59d1d79e","datavalue":{"value":{"text":"Polynomially solvable satisfiability problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114394$38CEBDFC-3158-42D2-BB08-F2465C823604","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dffeac353f5cd3eaee80209982ff8684003ec9ab","datavalue":{"value":"0662.68037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114394$FF3D5ABB-9744-4F6C-9B60-EC72AC787A2F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f8d6b82bfb020fbfc4a0e20c0dd9369f1e596931","datavalue":{"value":"10.1016/0020-0190(88)90113-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114394$8CE47E4B-55A0-486C-BE60-337AF646200C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1f9c055c1e99412bf37f14c70ff5d3ab10f6a171","datavalue":{"value":{"entity-type":"item","numeric-id":242826,"id":"Q242826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114394$996211AA-C33D-4AFD-939D-E1FC547FF609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1bd8af0b126294462c8738a3102eab28654cdb9e","datavalue":{"value":{"entity-type":"item","numeric-id":323503,"id":"Q323503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114394$7C004D69-E956-4CB3-9969-4E2AE7106449","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114394$B90702A5-C66B-4ADD-8062-F14C9E0D5553","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1114394$19B7FB52-6089-47BB-8DA2-B2855F7C3AE3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1b98f27dfdc36048be8020a91490e2b796ef4b44","datavalue":{"value":"We address the well known satisfiability problem (SAT), i.e., the problem of checking whether a given propositional formula is satisfiable. Although the general satisfiability problem is NP-complete, some particular cases of SAT are known to be easy. The most important of those cases is HORN-SAT, i.e., the satisfiability problem in the case of Horn clauses: actually, an instance of HORN-SAT can be solved in linear time. \\textit{S. Yamasaki} and \\textit{S. Doshita} [Inf. Control 59, 1-12 (1983; Zbl 0564.03010)] have introduced a new subclass of SAT, \\(S_ 0\\), which is polynomially solvable and which strictly includes HORN-SAT.    Here we introduce a family of subclasses of SAT, \\(\\Gamma_ 0\\), \\(\\Gamma_ 1\\),..., \\(\\Gamma_ k\\),..., such that \\(HORN\\)-SAT\\(=\\Gamma_ 0\\), \\(S_ 0=\\Gamma_ 1\\), \\(\\Gamma_ k\\supseteq \\Gamma_{k-1}\\), \\(k=1\\), 2,..., and \\(\\Gamma_ k\\) approaches to SAT as k increases. For each k, \\(\\Gamma_ k\\) is solvable in \\(O(n^* n^ k)\\) time, where n is the number of propositional letters, m is the number of clauses, and \\(n^*=O(n m)\\) is the size of the input. An algorithm to check whether a given instance of SAT belongs to \\(\\Gamma_ k\\), for any k, which runs in \\(O(n^* n^ k)\\) time, is also described.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114394$72E2B3D9-3ACF-47D0-BCE0-85C34FD4A8CA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114394$A47FF88E-876A-482E-A214-18F02501610F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114394$1F43807F-155C-429C-AB74-6B21327EE53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114394$88B2A8A7-54E2-4421-A55A-9939259D5267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"10eaeaf8bbf8231bbfc812aab8956e260b5a9f12","datavalue":{"value":"03B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114394$86DF2BAE-2B02-4288-94C3-7778602C52E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114394$D8E56F62-457E-49F5-A139-120B7096884A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4addf81a16429a0095c7c3a91ac934341b9fcd4d","datavalue":{"value":"4082968","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114394$EA37C086-CEE5-454C-9E13-7B03E37DC175","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114394$7AF7DF3E-A110-4BCD-ADCA-1A6BA96E7515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e431190495251d75e7d7f973ca704f4139885eb","datavalue":{"value":"Horn clauses","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114394$F311BF2F-E32D-4F9E-8217-F718C321157F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdfef3b62dccc66b23d61af21596b4014672eef3","datavalue":{"value":"polynomially solvable","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114394$C0DD76FE-C9EF-423F-AFF0-9A5897F88203","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114394$A33A7718-BEEE-455A-9FE9-C87355E39577","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1bb94d11104b37ee6a402c11dd209b789ce36541","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90113-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1114394$ED9E6102-0C2D-4554-8233-DFB3EF6CCAF0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c40191266961893bb4f48f3a62a972ab05a660a2","datavalue":{"value":"W2054160878","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114394$073210F2-A0C9-4F07-B0EF-9B102944C354","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3c464582ae733c7e854270d41591b96fb4b962f","datavalue":{"value":{"entity-type":"item","numeric-id":1097717,"id":"Q1097717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114394$6D66B352-1B82-4162-8130-0DA5D09DBF05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114394$0CBF29D2-65A8-4F7C-B427-14C643778612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a73f079fad88596351ff709cf186cec234a2805","datavalue":{"value":{"entity-type":"item","numeric-id":3723723,"id":"Q3723723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114394$F04CD721-2247-48E9-B645-10914F578577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b353bc1298597265c71a16d3c350d4e62f0e57f","datavalue":{"value":{"entity-type":"item","numeric-id":3677734,"id":"Q3677734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114394$32881F13-D396-4F47-893F-B98A519A4C17","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fd9e5cacfc9a515f723536fa9ba0f70d9f901d8","datavalue":{"value":{"entity-type":"item","numeric-id":1380432,"id":"Q1380432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ef37a3e9d81c7daedadd6c94f75da5e5790107e","datavalue":{"value":{"amount":"+0.8711671233177185","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114394$B3C471F7-50FF-4D6A-984F-E83726B7B787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a925a970a0df41f0a5c8293e886e68ad2b96fbd","datavalue":{"value":{"entity-type":"item","numeric-id":1208436,"id":"Q1208436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"baac6120c724117379132f801ca823a80a8ea66d","datavalue":{"value":{"amount":"+0.8687395453453064","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114394$1EE1FF6D-9CA6-482C-A71C-09E2CEE0DD8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df684ab8201b649acc8d339dca420dbf8bf70615","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"354c72e56bd28bc96d3ca999ccd7601c9bdba468","datavalue":{"value":{"amount":"+0.8537333607673645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114394$86A58573-8D5E-4C7B-8449-226C693DE343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fea1dd36d6008e5dfd29279c43a7080dd92ab2e3","datavalue":{"value":{"entity-type":"item","numeric-id":4375759,"id":"Q4375759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb2aad1b9bc90ffd63adde4e7df41e1cd95f038e","datavalue":{"value":{"amount":"+0.8358020186424255","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114394$AF3AC345-6C0F-4183-ACA0-4A9C222C8079","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d128c574f2b8cf58e4ac1be1405936a1d2197a9","datavalue":{"value":{"entity-type":"item","numeric-id":1861558,"id":"Q1861558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb2aad1b9bc90ffd63adde4e7df41e1cd95f038e","datavalue":{"value":{"amount":"+0.8358020186424255","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1114394$AB49E579-A2AB-4F25-A2DB-93C10BD3D2C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1114394","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1114394"}}}}}