{"entities":{"Q1099168":{"pageid":1109920,"ns":120,"title":"Item:Q1099168","lastrevid":69637254,"modified":"2026-04-13T08:22:08Z","type":"item","id":"Q1099168","labels":{"en":{"language":"en","value":"On the complexity of the maximum satisfiability problem for Horn formulas"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4039874"}},"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":"Q1099168$5C5552F9-2B84-43D8-AAC4-190DBE8B60BE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b3cdb2e09e7f0a52e99daa654788547bb39de8dc","datavalue":{"value":{"text":"On the complexity of the maximum satisfiability problem for Horn formulas","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099168$16588BF1-2E0A-49EB-9804-2F92576B8C07","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d5ca031be6c77d4511b2ea7dbf140ce9398034f","datavalue":{"value":"0638.03036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099168$279DBAB1-D707-4A5D-973F-FDFD38649370","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f9cb4204e5ad707ab21b1657fbd282b0d11e5203","datavalue":{"value":"10.1016/0020-0190(87)90028-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099168$18107389-BB19-42CC-A6C8-544CF0E72420","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d014b1a5c53d4583e103a493ca5a114390d7213","datavalue":{"value":{"entity-type":"item","numeric-id":185380,"id":"Q185380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099168$EC5DE22C-D6CE-48F3-B3B2-01C0462A061A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5e246b2156a66b2ef031cfcf9e9cd6a9e9aa0f2","datavalue":{"value":{"entity-type":"item","numeric-id":431807,"id":"Q431807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099168$6ECAB508-B5C0-4A2D-B49F-C0155954CD76","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":"Q1099168$0411697A-572A-4C82-8765-D7E63B064A4C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1099168$0B4E3AB5-5B2C-4230-AA23-BC65678D7772","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ddef5a7acca763e9ea429708eee525285cc7ca9","datavalue":{"value":"Some results concerning the corresponding complexity of algorithms which check the partial consistency of logic databases are presented. It is proved that even when some quite strong restrictions are imposed, the maximum satisfiability (MAX-SAT) problem for Horn formulas is NP- complete. Hence, when the Horn formula is either quadratic or all its clauses have precisely one complemented variable, it is shown that MAX- SAT is still an NP-complete problem. For elementary Horn formulas, the MAX-SAT problem can be solved by a polynomial-time algorithm, where an elementary Horn formula is a quadratic Horn formula such that every nonunit clause has exactly one positive literal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099168$A51CF781-4D43-4C43-8FEA-BD9965033B16","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099168$F3FB2486-A9FD-43F0-8928-1EFAB9A45A95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099168$C834081B-A418-4CFD-8B40-74383B1B1EFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099168$C7FD2E0A-767C-40B5-9311-3719106747AD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"097d5ad1a17318c051f795cd93a6b4d64da5f02c","datavalue":{"value":"4039874","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099168$03E73DA9-18E9-4EFB-8DD8-7D2CF4D1C9F0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099168$36BF6B88-FF63-4F42-B151-854D284C5551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91993be004af1453cf4fd79c07e1ba49b9211805","datavalue":{"value":"logic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099168$7F3C64A0-2886-46DB-A981-298F10A856B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61357657bf874e08c6639092dc1d7f3a7701446b","datavalue":{"value":"expert systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099168$698023D2-E1DA-4952-BCAC-2D2718177220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d57f349a81490ec8e32c01721bbf001e9d40687","datavalue":{"value":"partial consistency of logic databases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099168$A0D61BFF-7261-4637-A03C-10FD832938A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7266802113187a96c78397ed692b735dee12e876","datavalue":{"value":"maximum satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099168$9ACE67C9-3C53-424A-A7F4-3B32EDED9C80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ef3d1e723a50ff6e761b841dc7be35b8a1ffc8a","datavalue":{"value":"Horn formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099168$828C5C00-380D-4976-AE70-54FD0F90E275","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"00dcf12b9a602d9c5eb5566a233851af0f0ed4fd","datavalue":{"value":{"entity-type":"item","numeric-id":469832,"id":"Q469832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099168$D2C75891-C567-4D77-85D1-D42FE051D96E","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":"Q1099168$BDD5EEC5-957B-4D99-92D0-0F41D0CC21E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"40c92e296ccecebe9184c73e7397e9a5fb1dee56","datavalue":{"value":"https://doi.org/10.1016/0020-0190(87)90028-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1099168$87E84B1E-10B2-45AD-AD8A-624B9ECFE31F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dd936e76b4a7861fef63259216d9d0b5e4e18ef2","datavalue":{"value":"W2083756938","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099168$F0E60E2B-A027-4F2C-9469-B8DBAE27FF98","rank":"normal"}],"P223":[{"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":"Q1099168$EA313054-C16A-4E4D-8106-17DFBD7398AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"854bf29386092635a477e0881f3f0c76f5ed2664","datavalue":{"value":{"entity-type":"item","numeric-id":5624995,"id":"Q5624995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099168$AC593C61-FE91-4ADF-8DF1-669BD9E79570","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":"Q1099168$ABC5BCF2-BD1B-48DC-AEF8-7F433274D3BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8938235e226586e0d42dc09ecbb90514ca80ee6","datavalue":{"value":{"entity-type":"item","numeric-id":4094634,"id":"Q4094634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099168$BCAA214F-05C3-4ACE-ACC1-6CEA0996CC80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5deea374b82280f9bb78642ae53787a3c1d6cada","datavalue":{"value":{"entity-type":"item","numeric-id":3340205,"id":"Q3340205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099168$BB9E451F-FEF7-454B-9BCE-8107C5D0685D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099168$B3D0D518-4EBF-4096-9D4C-24ED141F4BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099168$C4C8158C-1282-4928-8DD5-AAEFC1AB0FC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb1971476988dd1583d8582c2332379ed61a85fd","datavalue":{"value":{"entity-type":"item","numeric-id":4090127,"id":"Q4090127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099168$A189C322-88BD-41C8-B771-BF04F19243E8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2105f0c71536059d0b6d9a52909981c1a5ac2ee","datavalue":{"value":{"entity-type":"item","numeric-id":3723723,"id":"Q3723723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e39e8d3274e5992bee8dbecf708eae4f3551255b","datavalue":{"value":{"amount":"+0.8218565583229065","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":"Q1099168$B30B1395-B874-47E2-849A-5257B1AE9AE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04415b4acfa317c05592d9e4057f2a56b8a072ef","datavalue":{"value":{"entity-type":"item","numeric-id":3815282,"id":"Q3815282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c56db597e7c09735fd19ba33add4e65ce2f7092","datavalue":{"value":{"amount":"+0.8080164790153503","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":"Q1099168$796E4F19-73E3-44BD-A8B7-93CC96CB7039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d47f218630e3a65921925fa215162a48c4394e4f","datavalue":{"value":{"entity-type":"item","numeric-id":997066,"id":"Q997066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b3fa5569c27f25ec1e03e49ca66c82c4ad9b02e","datavalue":{"value":{"amount":"+0.8043987154960632","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":"Q1099168$96EECC3E-F890-4103-BA46-575BB01E2333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e7b2504b97273c1f43d3acbf9ab35631eb89919","datavalue":{"value":{"entity-type":"item","numeric-id":5714756,"id":"Q5714756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98a86267f9917f6197c36cbc96cf470a5b05dd83","datavalue":{"value":{"amount":"+0.803533136844635","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":"Q1099168$5786AD24-C079-49BF-AE8A-42817D670A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2937afbdcfdb58cc1294d75eba114f32c3120f3","datavalue":{"value":{"entity-type":"item","numeric-id":452481,"id":"Q452481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e97cc1e01c6f0d89b0f9e8923065474437d5c3c","datavalue":{"value":{"amount":"+0.7998492121696472","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":"Q1099168$164446F3-1E83-4ED6-9BF3-64F4FAD63C57","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of the maximum satisfiability problem for Horn formulas","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_the_maximum_satisfiability_problem_for_Horn_formulas"}}}}}