{"entities":{"Q790612":{"pageid":792460,"ns":120,"title":"Item:Q790612","lastrevid":48687259,"modified":"2026-01-05T15:01:00Z","type":"item","id":"Q790612","labels":{"en":{"language":"en","value":"A simplified NP-complete satisfiability problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3848607"}},"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":"Q790612$D51A1DA3-938B-47D6-A9ED-A7D847ABE609","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"61275ded6ab1a176169da417cb3b60a2122e4534","datavalue":{"value":{"text":"A simplified NP-complete satisfiability problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q790612$0CFBE9A3-E58A-4F11-B677-C21B99522BA3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b48d7f7627981892a39ffd4dc02bcc75d18954f8","datavalue":{"value":"0534.68028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790612$E0CB8FB7-40DB-46E5-BF62-ED8BC2DA21CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ea24c6174aa8d9413e15720af9d5b97312191310","datavalue":{"value":"10.1016/0166-218X(84)90081-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790612$6C5C4FC7-1FAC-47B4-8887-9F8DB354DE8E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2439bf2fa3411fba0c2b1297578ae7ef0eaf65b","datavalue":{"value":{"entity-type":"item","numeric-id":201777,"id":"Q201777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790612$22E2FB01-FA0D-4AC8-A483-8BA490DC6FF7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790612$001A7DCA-9896-4A6A-9574-85B267D277AA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q790612$7BD07D4C-C0DC-4053-813D-92C297716411","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eb40c5e4e6fdf8b7440184f3ede7fe3b834ac3ab","datavalue":{"value":"A well known NP-complete is the satisfiability problem (SAT) for sets of clauses in propositional logic; it is frequently used to show the NP- completeness of other problems by polynomial reduction. Therefore it is of practical interest to refine SAT without losing NP-completeness; one such refinement consists in the restriction to sets of clauses with exactly three literals per clause [\\textit{S. A. Cook}, Proc. 3rd Ann. ACM Symp. Theory of Computing, 151-158 (1971; Zbl 0253.68020)]. Let m, n-SAT be the satisfiability-problem with exactly m literals per clause and at most n occurrences per atom. The author shows that 3,4-SAT is still NP- complete; furthermore he proves, that this is the strongest possible refinement, because the instance of 3,3-SAT are always satisfiable (so 3,3-SAT is trivial). Moreover the author presents a simple (deterministic) polynomial-time decision algorithm for the m, 2-SAT problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q790612$37CD1CB9-2A8B-4444-857D-78CFA818D216","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790612$9B10C251-FBB8-4E5A-AD28-27830FE1790B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790612$1100E1B8-8BB5-435F-BD05-DD8703EB13B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d8724ac1f861fd4485a474d1844744a1ace24834","datavalue":{"value":"03-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790612$DCF218F5-13FB-4ED3-BBF1-22A28E4B3C99","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f997a79b6c4581380b9fbf88b36e26900cc254e3","datavalue":{"value":"3848607","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790612$141D13CD-0E60-41F4-985D-FE3F032038D1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f0b4d6e6089943a261128dec792d30fd4cdc9763","datavalue":{"value":"satisfiability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q790612$F935C196-00AB-4FC7-B01B-13956F07C078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93c047fb19c5161b32c5245d5c8c28b4500157fe","datavalue":{"value":"propositional logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q790612$FFD3D8E6-99BF-48BE-BDCB-87BF69A788C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q790612$4A7E383E-5F84-405A-B6E6-FA983A7C6C22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccd03fed1421dbfb861961d1b69dcf6589030a96","datavalue":{"value":"sets of clauses","type":"string"},"datatype":"string"},"type":"statement","id":"Q790612$D8E3CDDF-7267-42B8-A891-F559C47F0329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26ae8fa0214d020e3ce62b16427ef2b40e2abe0e","datavalue":{"value":"polynomial-time decision algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q790612$40FBD371-68D2-43DD-8804-C970A6B547C5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2131474b61f9492afe33179f8e943fe4605532de","datavalue":{"value":{"entity-type":"item","numeric-id":167060,"id":"Q167060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790612$A6470C09-375F-4B33-BD68-3D46E32AF6C0","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":"Q790612$A960FED3-0CD7-4E8C-B621-08BB4D4245DB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790612$C30F5B53-D8D9-42B7-BAD1-E563A7DA5FBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790612$643D753B-BF35-4112-B3AC-354A26959B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790612$B70194E2-7629-49B1-ADE4-6342357F0794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4534d792f5262a1f297a74f9b43efedcc5cd94ec","datavalue":{"value":{"entity-type":"item","numeric-id":4760022,"id":"Q4760022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790612$15F0B9C7-5D9A-4FE9-8EB5-7FD505F805AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c52b21e2b050930655d553363cf317d38372f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3885184,"id":"Q3885184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790612$31135232-3E00-4127-B229-D5FAA49043EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8b5333eb1b8ed8e5a5b9dc077a98e596db9c9cc","datavalue":{"value":{"entity-type":"item","numeric-id":1250163,"id":"Q1250163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q790612$EF52E567-10BE-427A-8DFD-878295C39E3E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c6fb1c1b5f91e5fd07abeddaa5bbcbc5341f8085","datavalue":{"value":"https://doi.org/10.1016/0166-218x(84)90081-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q790612$F27EC6C8-88BF-456B-9E5A-3EFBAC74ADDA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c55357a7f5197cfbdd3673336aefaa465ca408d8","datavalue":{"value":"W2003979824","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790612$2DC7AFB2-89A3-4AC3-8342-E6212C95ADFE","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1254a045cb7c0d829fc75c94eb3cb85b600a1c4e","datavalue":{"value":"Q127443560","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q790612$A40B7B49-E1A8-4C8A-9406-B85D77EA829B","rank":"normal"}],"P1643":[{"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":"d920fdb6b65c6e7f55df7433c4c9350ed1b98be7","datavalue":{"value":{"amount":"+0.8995794653892517","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":"Q790612$111A4763-5B53-4BC9-8F23-69AEDB668A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45d8891ac6df97a878ccf7a91e4948e04efd55f0","datavalue":{"value":{"entity-type":"item","numeric-id":293164,"id":"Q293164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2a9161c4b67e4e804283b0fc506e15fb27a600b","datavalue":{"value":{"amount":"+0.8777827620506287","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":"Q790612$B3AA2C81-6B69-44CB-9A24-B1335453133A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb6b6bcdb87c4692903667b4772f341680ad7c51","datavalue":{"value":{"entity-type":"item","numeric-id":4037693,"id":"Q4037693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d31526c08c76eed73ab2635d7be862722c2e0a4d","datavalue":{"value":{"amount":"+0.8519536852836609","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":"Q790612$EE16DC2C-007F-4676-9E65-452D7BBA9888","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"438ca1492819dc9e73a8c603ef8ddaa7f71a92bf","datavalue":{"value":{"entity-type":"item","numeric-id":4032119,"id":"Q4032119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d0b807460794057d5a42674e5fbf72c78d8d4d6","datavalue":{"value":{"amount":"+0.8518224358558655","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":"Q790612$B0E2CB44-D384-4153-890B-B0AF5B70C436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f68dd49e8d790217f4c6e141204af1920c329f5f","datavalue":{"value":{"entity-type":"item","numeric-id":4283247,"id":"Q4283247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b79427661309ece6bfef052dc98c08bedb2ec1a4","datavalue":{"value":{"amount":"+0.847015917301178","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":"Q790612$D196D7CD-4EB9-4855-8EF6-5B942796C8DC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:790612","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:790612"}}}}}