{"entities":{"Q4946793":{"pageid":6976375,"ns":120,"title":"Item:Q4946793","lastrevid":91128812,"modified":"2026-06-04T22:19:59Z","type":"item","id":"Q4946793","labels":{"en":{"language":"en","value":"On a criterion of NP-completeness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1422883"}},"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":"Q4946793$596161D4-D9A0-428F-867B-6F2BDA2592EC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e50ae391e3796479f6d84b9773e6d5d6973e940","datavalue":{"value":{"text":"On a criterion of NP-completeness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4946793$4FC42E2E-0353-4018-A5FA-FD8324424155","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8e80f6308868000744e75422782334ea30a64b8a","datavalue":{"value":"0968.68515","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946793$E7C6E9C5-AFC0-4265-8D18-782120C42D5B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"755a726a99e1fa6ac817c7f74927304c6d00184c","datavalue":{"value":"10.1007/BF02514208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946793$18378022-A23C-44D9-89C4-C74552B3BC56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"870738c67a9eb4f06d5afd570883e0b3e0547d8b","datavalue":{"value":{"entity-type":"item","numeric-id":1149946,"id":"Q1149946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4946793$999FADA7-9DC7-4969-8104-BCA174B45D35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2fc00c004868519b23ead1e51ed4bf1561b2511","datavalue":{"value":{"entity-type":"item","numeric-id":4946792,"id":"Q4946792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4946793$E437C238-8DD0-4344-AFC6-A99B4FF3D280","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7c0466bf8ef14469f86c8db17e45659eb51aefea","datavalue":{"value":{"entity-type":"item","numeric-id":317357,"id":"Q317357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4946793$BEE533B2-D355-47BA-B506-F94DA2899EB8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"35fafbbe8209085733f3754bac7d6ba0f1c137cb","datavalue":{"value":{"time":"+2000-03-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4946793$CFD1E6C5-8FC1-4FF1-B1D5-79570D1ADF63","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946793$CA31241F-ACC7-4003-8F94-022673F5F3F3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b307b0c29209c891da7018778baa1c9c311bbe1b","datavalue":{"value":"1422883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946793$B63E6805-1C86-4E0B-8B92-4DF7FCFDC068","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3cfae55afe2e2e995af526edc3930f19591dca4","datavalue":{"value":"completeness of sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q4946793$34FE873D-5E4D-4B0A-889F-AA867F045370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fcca4be8867370736c82a7446e76349d1b3aec2","datavalue":{"value":"Cook theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4946793$044CD72D-C55B-4E3B-8C16-0DDF7D48FA48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4946793$1D3AE137-F94D-43B0-9F76-8974843857CB","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":"Q4946793$5F93A27C-5BC9-4DB9-907F-2FF878D5E3CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4a647769ea787ee1065fee75f7d36467dbede577","datavalue":{"value":"https://doi.org/10.1007/bf02514208","type":"string"},"datatype":"url"},"type":"statement","id":"Q4946793$F4234A59-CB4D-44B0-A83D-437A6D165E46","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"585c098389748917fe823e698bd46e595c00ee33","datavalue":{"value":"W2095231818","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946793$44CE37B4-656D-4A1B-B19E-8C79F828E4AD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08e6d9c9f089659f34ed51aeccace6fcd6181f03","datavalue":{"value":{"entity-type":"item","numeric-id":1097029,"id":"Q1097029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b65f20a204a50df88b879feaeaee31abbbaf6eda","datavalue":{"value":{"amount":"+0.7749034762382507","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":"Q4946793$D3406A45-C34D-4A08-81A2-EA8AF661A720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"800da3da189c3717ae4b944549a97eed4a205a7a","datavalue":{"value":{"entity-type":"item","numeric-id":3830528,"id":"Q3830528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6ae3e563128e7d5b92c54531ff55862af03a8d2","datavalue":{"value":{"amount":"+0.765763521194458","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":"Q4946793$EB6A9D70-EA57-43FB-94CA-C59E8B0564A2","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":"d653d3041cc2ea2de610164eb85a28d1920485cd","datavalue":{"value":{"amount":"+0.7593267560005188","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":"Q4946793$AB22B9D4-A931-4CEE-9332-3373D170C398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b13456fe5fe9e3550c2469657db4a6d3d1543bb","datavalue":{"value":{"entity-type":"item","numeric-id":1124342,"id":"Q1124342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae37487203f387984001b50eebf3c379c71cf0ba","datavalue":{"value":{"amount":"+0.757844090461731","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":"Q4946793$7EA88A25-288E-4471-893D-35BA2611CAC5","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":"8e6c8b502f677f0edb38dbd7bacc4f646c4207b3","datavalue":{"value":{"amount":"+0.7526705265045166","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":"Q4946793$B22D57CC-784C-47B9-AF8A-9D25D5427AD0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On a criterion of NP-completeness","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_a_criterion_of_NP-completeness"}}}}}