{"entities":{"Q1322290":{"pageid":1333040,"ns":120,"title":"Item:Q1322290","lastrevid":70136250,"modified":"2026-04-13T12:41:31Z","type":"item","id":"Q1322290","labels":{"en":{"language":"en","value":"The \\(k\\)-SATISFIABILITY problem remains NP-complete for dense families"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 562678"}},"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":"Q1322290$D994DCE0-C943-4EB6-9F00-8A118AE6D0BC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e616f63053e0d6e692a14864c03b26e86be856c","datavalue":{"value":{"text":"The \\(k\\)-SATISFIABILITY problem remains NP-complete for dense families","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322290$A8601E8F-B3CB-44D4-BA6A-2D8F1FA34636","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6e514423ca831de5e8cab9c018db136908197ca1","datavalue":{"value":"0803.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322290$46235E5E-977D-4254-971B-EB68D17AE7DD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1598a66ef9fe30f98f4c0dfb41302ba15eeb9093","datavalue":{"value":"10.1016/0012-365X(94)90175-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322290$EF6701AA-C0B9-4571-B16A-190CB6651CD2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b09124aade2f9a2d1dad9d1d88ddbbb2bdabd00","datavalue":{"value":{"entity-type":"item","numeric-id":228794,"id":"Q228794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322290$126D46FC-7C7F-4DE2-A10A-0AB3FA42B974","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322290$CAA6722C-0906-497C-B3F4-182E8E82AF10","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6fec002a86967a3d68ab1d50269b51e2d2e883c0","datavalue":{"value":{"time":"+1995-01-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1322290$B6FCF3FD-4935-4243-9FE8-EC2729F2A5B0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322290$61F09CB5-252C-472C-87B8-DA3F9E965E74","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"16ae55c7b2accac68937aa0eea3fba3ea21a6206","datavalue":{"value":"562678","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322290$60203323-9190-409C-8BD4-30D2F5809E38","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"183cc7d6ec0dd106effa32b9e95d2e908469b9a8","datavalue":{"value":"\\(k\\)-SATISFIABILITY problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322290$8B91D3EE-5F09-4FDF-BF2E-B70471D1D81C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322290$315139A5-4708-45A8-ACFC-3E4B74A1E6F3","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":"Q1322290$7699E139-1D6C-4F7C-B56E-98835D72323E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e7d3dffde4b639a5080d558096cb7a34be71d72","datavalue":{"value":{"entity-type":"item","numeric-id":4146529,"id":"Q4146529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322290$D73B5DEC-1C19-4F8D-9C82-EAFB469C7341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b5fa8fb11c78aae21b2eb5b72be3dfa58615b97","datavalue":{"value":{"entity-type":"item","numeric-id":4037693,"id":"Q4037693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322290$D13A546F-1852-40E6-985D-5BCC8BA18F52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d50041fd827b9a880db5475227f379529c471731","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322290$C9DC6726-8402-4DF5-A66A-66256C5AA4D1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24ec9455f54c32283ad7953bf6c8ed6237e5816a","datavalue":{"value":{"entity-type":"item","numeric-id":790612,"id":"Q790612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d28084b4949bad416c39c56a93012a3d41b5b3d8","datavalue":{"value":{"amount":"+0.8443045616149902","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":"Q1322290$7ECCB7A5-C2E2-42CC-B71C-79DDE89EFE6C","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":"41f8e3d974ca724b3824a571fe26a394511b4fea","datavalue":{"value":{"amount":"+0.8384251594543457","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":"Q1322290$843C852B-6E57-46C7-8413-5604B699BA02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ce42d2dba3f8690f5e16c123b3edaaa61030a89","datavalue":{"value":{"entity-type":"item","numeric-id":3507322,"id":"Q3507322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5976bc9d36bbb43e3eebc83179098cc67567308","datavalue":{"value":{"amount":"+0.8255385756492615","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":"Q1322290$E09713FA-5196-47B9-955D-3C1020751F13","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":"ba07c47c93eb321001b9af312d65ddbd7aedf964","datavalue":{"value":{"amount":"+0.8247286677360535","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":"Q1322290$5B7D8601-1FA7-4121-AFDD-5D5BCFF263AE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The \\(k\\)-SATISFIABILITY problem remains NP-complete for dense families","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_%5C(k%5C)-SATISFIABILITY_problem_remains_NP-complete_for_dense_families"}}}}}