{"entities":{"Q3507322":{"pageid":5537226,"ns":120,"title":"Item:Q3507322","lastrevid":80611226,"modified":"2026-05-06T16:35:57Z","type":"item","id":"Q3507322","labels":{"en":{"language":"en","value":"NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT\u2009\u2265\u2009k ,r-UNLSAT\u2009\u2265\u2009k )"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5290791"}},"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":"Q3507322$5C25B54B-0972-4E6C-9A53-8A897571E3B0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ed723b97d0dae30cb46a252eb6453fbc6be1cf3c","datavalue":{"value":{"text":"NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT\u2009\u2265\u2009k ,r-UNLSAT\u2009\u2265\u2009k )","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3507322$C8AD6509-8D64-4E44-A5A3-A96A668EDF77","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ed32550ef993fba3a7ddf4dcdd56589472c1ba92","datavalue":{"value":"1143.68403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3507322$1D69BE14-49DE-495D-8393-DF076655F16A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5455a1bfbbf4c8197260489c0ddfe69b47b14713","datavalue":{"value":"10.1007/978-3-540-69311-6_11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3507322$B73A80D6-19DC-4B30-B37E-17826BCEDEF5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"909a2c4181e2781f3ee08cd82446ea5b077a108c","datavalue":{"value":{"entity-type":"item","numeric-id":3507321,"id":"Q3507321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3507322$5591CB9D-8E3D-4443-811D-CF75E821B503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d1cfac4fcc4acbf6b4ed2adbfa6f6821da971d1","datavalue":{"value":{"entity-type":"item","numeric-id":1040958,"id":"Q1040958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3507322$26BCC71D-B4F7-42D8-91E0-804222199F90","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"039449918372fd36372960c159b1f017e2991028","datavalue":{"value":{"entity-type":"item","numeric-id":3188827,"id":"Q3188827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3507322$F9FBB515-ED72-418C-B64F-C8AC96A50259","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"94adc6da8cc08e29523a0a31b3af6d1a94363069","datavalue":{"value":{"time":"+2008-06-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3507322$A2E7A0C0-6314-4274-BC93-AEDACB0C84BF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3507322$6AA23D7B-0196-4A26-9E0E-741329802B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3507322$82811D98-1CD2-4F97-90F5-B6C43D8378D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"75fa82bb2d929ec50f139daba906763d03c11966","datavalue":{"value":"5290791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3507322$158603E5-CAB3-492A-AB8C-F0D2B3CF046E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85c94c4548a4129fc8b6cced20d5c03e5c3efda0","datavalue":{"value":"PCP theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3507322$BD5002FA-6052-4D12-8140-39D5A42915C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f2d080f4845bcb5a4710f9e87de029dda89afa0","datavalue":{"value":"linear CNF formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q3507322$0D52B6E5-5E3D-4CEB-BACC-FFA446468195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9247b423ba4324f3bb2756a798be2e5f743e2455","datavalue":{"value":"LSAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q3507322$50CC09E9-57B8-4D1A-981C-4AAC90A2FE51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3507322$8F7C946D-7FF9-45E9-B98D-48291D2E477E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfc1c912dbc1f534d35dfe4c7b828346e80b5fd8","datavalue":{"value":"reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q3507322$6BDEC83C-9808-4ED6-B802-35AD35AE0F3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22c1e5a9094fca3ffa6e8af63ae29a237fb1e3ce","datavalue":{"value":"minimal unsatisfiable (MU) formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q3507322$E94ECC7A-DEED-4E8E-A26F-112C92838B9F","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":"Q3507322$FBF3994D-EEF8-4D55-ACBD-3CAD18B155A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7a08ac399da472d8eebcbc5db8cca91dfb4d3e3b","datavalue":{"value":"https://doi.org/10.1007/978-3-540-69311-6_11","type":"string"},"datatype":"url"},"type":"statement","id":"Q3507322$665335F9-E4A3-46AB-890E-F1A546135290","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9d4518277aa79de6c40077932a94290469fdd075","datavalue":{"value":"W1496485637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3507322$D4F65F19-1997-4E48-8E29-551F952DFA82","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"755bb9e2da3e04a3fdd2a172851bfa20892491a7","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"714cdaa6e424959dc2d6c40792cf9aa076409585","datavalue":{"value":{"amount":"+0.8788361","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$05C1649E-A4BD-4642-AA3E-5ABF054CDD9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20fc3c596a9edb8e5583cac032889717c67ce3fc","datavalue":{"value":{"entity-type":"item","numeric-id":1711421,"id":"Q1711421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcd315418878c5cb518c287efc1dedd05dbad2b6","datavalue":{"value":{"amount":"+0.8695179","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$84F627E2-2D5F-49C5-B5B7-EF2DC69E55C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7488a95a6fb23c2a75057e349b7ab3a82a4bd841","datavalue":{"value":{"entity-type":"item","numeric-id":2475410,"id":"Q2475410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86111fe9ddfc3240d22c7738f750d1eb278e23fd","datavalue":{"value":{"amount":"+0.86028445","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$BB7C910B-4C00-47DE-9981-0EC03FAFF8E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18de8fc0c757771836167eb7eea61e75121d089e","datavalue":{"value":{"entity-type":"item","numeric-id":903370,"id":"Q903370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21d5ce0823567d92754e3624b918ca30390f12ad","datavalue":{"value":{"amount":"+0.8509108","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$21D22781-09AD-4DA1-8177-375022F0DC35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdd0351e6ef403a51bb0dfe884b819c3f3ae04c6","datavalue":{"value":{"entity-type":"item","numeric-id":1585561,"id":"Q1585561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a1768f89d249b9e2a4b71b94fed2dac354c5307","datavalue":{"value":{"amount":"+0.8464759","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$A4D25C3F-F6BA-4DBE-9DF1-0162BF6698B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dc70630881469eb61a3b88d9577a3b7336c8241","datavalue":{"value":{"entity-type":"item","numeric-id":3502698,"id":"Q3502698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"907b8b57e1910c1cd69448b374d57ce302eb2028","datavalue":{"value":{"amount":"+0.8457304","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$3F0364F3-2561-4DB3-B7A7-5FC7D447F626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"451fc3a6fbdfb9bbf958bb10b2350c3b5488d1c9","datavalue":{"value":{"entity-type":"item","numeric-id":3392942,"id":"Q3392942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0da0a9bfd9cd2138d9cc27d416f7ee158d4b186d","datavalue":{"value":{"amount":"+0.8452046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$68792FE8-6482-459E-B3C2-7ADEFA4B5A06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8946f079ec164c412e39efde00171b3a9e677f91","datavalue":{"value":{"entity-type":"item","numeric-id":5151063,"id":"Q5151063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da8726c8cdda837ece5913a346dfa2d6cb9797fb","datavalue":{"value":{"amount":"+0.84276897","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$D8C75396-A4F4-49A8-979F-68FE5AB30884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f154465087b074874b8b3ba81ee1aa3deab47c1","datavalue":{"value":{"entity-type":"item","numeric-id":5691296,"id":"Q5691296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa5854938813f55f3114655e04dfeca9b7dda2a6","datavalue":{"value":{"amount":"+0.8426471","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$A1E544AE-3DA5-4F37-BB83-287C0B623DB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8deccf2299418ba261318ae6062ae293cd70989","datavalue":{"value":{"entity-type":"item","numeric-id":5425474,"id":"Q5425474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2949ef839fcd4347659db2c0f4c3eea6829014f3","datavalue":{"value":{"amount":"+0.83787006","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3507322$49499C28-D1C5-4F90-97C4-79A84F353073","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT \u2265 k ,r-UNLSAT \u2265 k )","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/NP-Completeness_of_(k-SAT,r-UNk-SAT)_and_(LSAT_%E2%89%A5_k_,r-UNLSAT_%E2%89%A5_k_)"}}}}}