{"entities":{"Q1055405":{"pageid":1057253,"ns":120,"title":"Item:Q1055405","lastrevid":69528966,"modified":"2026-04-13T07:37:11Z","type":"item","id":"Q1055405","labels":{"en":{"language":"en","value":"Strong nondeterministic polynomial-time reducibilities"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3823759"}},"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":"Q1055405$B302A6EF-F14C-4F0F-B481-19AFD3C97EBA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b5024021c412ed6fa8351360746c1fefec77760e","datavalue":{"value":{"text":"Strong nondeterministic polynomial-time reducibilities","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1055405$0E7BB131-DAD2-4E39-8FD1-EFDBA1AB7DD9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a3fd39f6cbd28ac0af07fb7da3c0386becda3db","datavalue":{"value":"0521.03028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1055405$2724D8BA-A88E-4428-B2E0-75395058C55E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a2ff750d411936405fc6f671df1b8fc0ec1740c7","datavalue":{"value":"10.1016/0304-3975(82)90085-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1055405$BB6E7298-E1D8-4BB9-AD4B-BA61522B3A46","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ab62c892d378963e4ddd263f29ad88202d8991f","datavalue":{"value":{"entity-type":"item","numeric-id":1055404,"id":"Q1055404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$522EE930-AE9F-46E8-9282-56B0E913B6EC","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":"Q1055405$43310B8A-662D-46BC-8BC8-0C4CFC475F6A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"47f57cd36df9e30d446df3867dc3917e4ea74654","datavalue":{"value":{"time":"+1982-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":"Q1055405$F96F5474-F8C4-45A7-8825-90313A938041","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"379be2ae88ac653823960287ba517e23fc9265f4","datavalue":{"value":"03D30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1055405$FB19A2C0-8636-45BE-8CBF-0735BBA74AF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1055405$5A78FF9A-12E3-4465-AE4B-E3244BD8FFE9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"df3d8aa0da4c400ba816b2b36172fb27a14eae8f","datavalue":{"value":"3823759","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1055405$E976E0DF-B4E1-4E03-839A-2B8BB6140D96","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5248b9a0ba3fe2c834f2ad8592de885508a11d29","datavalue":{"value":"strong nondeterministic polynomial-time reducibilities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1055405$AE4ABE52-1B14-4C80-B130-6AFA297BCE22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1433bf2cc493ec1c1bbb4d08a8421a8c07cc6a52","datavalue":{"value":"NP-hard sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1055405$EE4DDF6E-1889-4AB4-B4A5-542B3B8263A8","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":"Q1055405$F91BFFFF-5DB7-4D43-9619-BA1F27BDB75D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9537321046cc2b57999e91d990b8b95c4e897938","datavalue":{"value":"https://doi.org/10.1016/0304-3975(82)90085-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1055405$D958BB71-A57F-47E4-9978-34B4671DA033","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"23dfbfb209a5387a1093863440b523ebc30914f9","datavalue":{"value":"W2041317738","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1055405$EA08D52F-CD44-41A0-B971-03D1908FD275","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$C7B39B09-FB22-453F-9C8B-0E769C32522A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b7948d2ae997be513a92df2486b836c4e1eaa12","datavalue":{"value":{"entity-type":"item","numeric-id":5667480,"id":"Q5667480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$9DA3526A-5F5D-459E-93CF-5E5E87A1A74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$538E1925-34A1-4079-B27A-CE158DCEA03C","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":"Q1055405$7CEA5749-25BB-4DB5-A81B-FA900690C6CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$E913CEDB-7666-41FE-89D8-35B2148DC6D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f3f8c402957e2c95095405c7dd38cb2d24866a8","datavalue":{"value":{"entity-type":"item","numeric-id":1149766,"id":"Q1149766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$6820A2CE-8CFA-4E56-B297-DA47C3E190F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bf8f4f51c4746451b278e449d586c5f3e2ac653","datavalue":{"value":{"entity-type":"item","numeric-id":4167585,"id":"Q4167585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$3888196A-D5EC-4E0B-A95C-DFB3FF75541E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd520b49bc58e84d7c227fcb0bc974b432f91cc2","datavalue":{"value":{"entity-type":"item","numeric-id":1166515,"id":"Q1166515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$C5370328-B8AB-4ABC-97BC-C725F9C0AEC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$8ECBC615-8754-4015-8D2F-1214D234C282","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3fdeac57e6ae30181fb2db5f7f4e10e134e5670","datavalue":{"value":{"entity-type":"item","numeric-id":1232181,"id":"Q1232181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1055405$6ED51598-E83A-4B99-949E-46852D2C1D16","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Strong nondeterministic polynomial-time reducibilities","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Strong_nondeterministic_polynomial-time_reducibilities"}}}}}