{"entities":{"Q1099614":{"pageid":1110366,"ns":120,"title":"Item:Q1099614","lastrevid":66130353,"modified":"2026-04-12T07:45:10Z","type":"item","id":"Q1099614","labels":{"en":{"language":"en","value":"On simple and creative sets in NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4041262"}},"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":"Q1099614$80E13291-B893-43CF-A4D3-3B3388959C12","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b447692799f4a8976093876bbae6fb3c674083ad","datavalue":{"value":{"text":"On simple and creative sets in NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099614$96FDF0BA-B211-4AE4-AB35-BAD97B772D18","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5be09240151bcfcee7d3396fd2b5d867a703140c","datavalue":{"value":"0638.68034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099614$CC295D15-50E5-465D-9C0C-6025AA18CEA8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d235a2ca18f84392a51b12c75f1aa13749b7f7dc","datavalue":{"value":"10.1016/0304-3975(86)90144-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099614$2CCAFAD1-E984-41E7-AB6B-A42DC36BA759","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$FBBBA489-80A0-4847-82A8-CD224DAF9E66","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1099614$341F77BC-241D-411B-A373-D7DE5F1487D2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"283e9260dbc19dbb5dad28fd6f6be8744a857303","datavalue":{"value":"Two structurally defined types of NP-sets are studied. k-simple sets are defined and shown to exist in NP. Other properties of these sets are investigated. k-creative sets, as previously defined by \\textit{D. Joseph} and \\textit{P. Young} [ibid. 39, 225-237 (1985; Zbl 0597.68042)], are next considered. A new condition is given which implies that a set is k- creative. Several previously considered NP-complete sets are proved to be k-creative.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099614$C7D7BE9C-B058-40E7-86B0-F38AC4A437E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099614$B36748A1-E207-4879-B957-AF22B8CED8F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099614$6C2DC5EC-A195-468E-82ED-2AE093D89402","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"00bf9ef49c3f340cad910f59bcbce86790401f9c","datavalue":{"value":"4041262","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099614$3ADB86BD-208D-4090-8F7A-973D4D656B01","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48d7bfe3a6b2df1f0651c2820a56db8435443ef9","datavalue":{"value":"k-simple sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099614$BF433EDE-07F7-4F0C-94F4-EDC235455171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41d9aedb6824d88ffdf97bd719a4fed2bb54c845","datavalue":{"value":"k-creative sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099614$BC94DDDB-BB64-4231-8B0A-C3C21003BEE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18b896e4875df610358fccf59713481feead9685","datavalue":{"value":"NP-complete sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099614$F0DDB506-71E2-4DF7-882F-AB863FAABC78","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"24978249bb6f26d3c70c78605ce95b13704fc350","datavalue":{"value":{"entity-type":"item","numeric-id":161379,"id":"Q161379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$6EE4F047-473F-46BC-856F-2D613FA92DED","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":"Q1099614$47953367-6E16-4AD0-89CF-73D1F05F23CB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d31be4a4c6a15322dde600cc9daa73cbe59e6785","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90144-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1099614$C357E31A-6F03-4BC4-99BA-E097B60466C0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aa05735eb97bb3d2132a9addb6e8034e32160006","datavalue":{"value":"W2005127553","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099614$B85F1B7E-44B1-4ACD-AC35-A3A9305A3531","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b77c359d113f74e32b5b8b8a0ffee20f29b60e6","datavalue":{"value":{"entity-type":"item","numeric-id":3690222,"id":"Q3690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$C7156B71-4F24-44F8-85AB-13ABF6C845F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$6EED3F5C-0D06-4850-A68D-D11297685DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f0d71b5e1cf68927e05cce9da9c6f8031ac8361","datavalue":{"value":{"entity-type":"item","numeric-id":5186732,"id":"Q5186732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$8258E5CB-1360-4E36-8EB0-EFE3316D0DEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bde708178fd22b5a6473ace4f76c9d9acbc0b80","datavalue":{"value":{"entity-type":"item","numeric-id":3347296,"id":"Q3347296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$173E8887-D693-497F-ACBE-18E2AF5A88DC","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":"Q1099614$8B91477C-A6A8-4F43-906A-644AD8070654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6017ede322a0601181d423bdbdeb7f89fc0690cc","datavalue":{"value":{"entity-type":"item","numeric-id":1163015,"id":"Q1163015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$D0F9D3D9-2E3E-48D9-8D1A-4DD96422CD1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f55297a1cd12495ecc078bcc00b99e9c77336ac","datavalue":{"value":{"entity-type":"item","numeric-id":3026341,"id":"Q3026341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$19717DB9-7815-44EA-8963-5401A0FC1433","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2bcba6abf24137e5ea317e56b32f617a34d2b1e","datavalue":{"value":{"entity-type":"item","numeric-id":795829,"id":"Q795829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$66E8AB3B-8D3E-4D0B-9413-C2A40F742DF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb51cb599580481aadcbb3a7e805e65dbcbf5ce5","datavalue":{"value":{"entity-type":"item","numeric-id":1079364,"id":"Q1079364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$8978C8BE-E11F-46E6-8C9C-5034126495C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3da510a58b16c0736f10bd517df8e982dda6dd9c","datavalue":{"value":{"entity-type":"item","numeric-id":3922170,"id":"Q3922170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$66A18F78-2391-4507-A108-172535854E38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$0F49F92A-5486-4711-9B36-3A27395C10F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71f28db7f96068e5ce3938c306e6d15e9aefa614","datavalue":{"value":{"entity-type":"item","numeric-id":3915990,"id":"Q3915990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$544E3AFB-32F2-42E7-991B-E2C1B401B3DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d938e2cf16a516c25169e92ed68817a27d01f44d","datavalue":{"value":{"entity-type":"item","numeric-id":5845382,"id":"Q5845382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099614$99E69895-78CD-46D0-8593-B14D9507BFEF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b822841fddea48e0f0de298194ea8afa91f1652","datavalue":{"value":{"entity-type":"item","numeric-id":3026341,"id":"Q3026341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcdb702a3ddd8e16ec5ab93be49a578bf0e78524","datavalue":{"value":{"amount":"+0.9994717240333556","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":"Q1099614$0D927CA5-6808-4CAA-BBF6-A3B14912EED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3588b73cc8b4751cef053e43842b7cc72506545b","datavalue":{"value":{"entity-type":"item","numeric-id":4895816,"id":"Q4895816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d035c54006499a576763c7d0e3efd7bed6fb75f","datavalue":{"value":{"amount":"+0.8826506733894348","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":"Q1099614$CA15FC90-DB2A-4A5E-B7A9-0B069BD5F772","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"622f2916f54ea25b4ffc040e4dfa93312e6a0c2f","datavalue":{"value":{"entity-type":"item","numeric-id":1183565,"id":"Q1183565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75248beb6b562f3a9d6903c17de5542b68ed3d2b","datavalue":{"value":{"amount":"+0.8050857782363892","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":"Q1099614$04750DD0-CECE-4865-81B3-E29AB20D5AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6870442d05a1854d92a812271e3a661047391dc0","datavalue":{"value":{"entity-type":"item","numeric-id":4867411,"id":"Q4867411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38a3a9d0ce4aef337af81ae01a02b1c9b6d45a6a","datavalue":{"value":{"amount":"+0.7949939966201782","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":"Q1099614$41F5C016-C0C2-418C-A224-CB7AE4D36CD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd108a317c33a10f3e61cc52d66fce78cc24002a","datavalue":{"value":{"entity-type":"item","numeric-id":1079364,"id":"Q1079364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d1ca4460f4d9682c122b4a64c8c3c414a82627c","datavalue":{"value":{"amount":"+0.7917734980583191","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":"Q1099614$1E1C4136-2E90-42B4-8D1C-96EEDFBBB895","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On simple and creative sets in NP","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_simple_and_creative_sets_in_NP"}}}}}