{"entities":{"Q3489449":{"pageid":5519349,"ns":120,"title":"Item:Q3489449","lastrevid":49412053,"modified":"2026-01-07T03:01:20Z","type":"item","id":"Q3489449","labels":{"en":{"language":"en","value":"Characterizing polynomial complexity classes by reducibilities"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4162261"}},"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":"Q3489449$A8B838E7-BDB3-4544-A83A-31053E1DF1D5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d4c2ba8371600cf8d2785c073725ae74c0ac1231","datavalue":{"value":{"text":"Characterizing polynomial complexity classes by reducibilities","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3489449$027E9E63-F6E5-46E4-B7A2-1D7D9F87F7AF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f2e08ce4d8a576b4ecd6226b5f5a1096803a1bc8","datavalue":{"value":"0707.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3489449$784A7E8A-1207-4C61-AF71-07884EA85D30","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"688408b8b4fc64b4f4da56dfe8869227abb63c61","datavalue":{"value":"10.1007/BF02090773","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3489449$FBCB9FDB-240B-40F1-A6FB-1EF1A9B176C8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab539a58a8a767731665253837c1bc29c4d22a7e","datavalue":{"value":{"entity-type":"item","numeric-id":593774,"id":"Q593774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$80C52E24-899F-4A80-AD4D-50622157EA5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d2b0422b59a9ea5fdddf3381570b20105869132d","datavalue":{"value":{"entity-type":"item","numeric-id":1193868,"id":"Q1193868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$E92A8762-D31B-4D00-AF23-514E475809BF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"5a8d775b0b8ac1723ca563ec42b8bfa391952af8","datavalue":{"value":{"entity-type":"item","numeric-id":3026825,"id":"Q3026825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$D54C3EEB-3314-4F04-8D7D-3BB144E22C91","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q3489449$D983518A-88CF-4F90-AA6C-85A473B49ABF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3489449$DCFC2FFF-1EB0-4976-86FA-E540E53E63A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3489449$7BE07590-D633-4AB0-8FD9-CD2545D4169B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"643ac8034c76c50eeb21e090b90ce9ab8a55179b","datavalue":{"value":"4162261","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3489449$6EF83054-F946-429E-A47A-49567AB36C36","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b9523b81abac7dcf2946305ecf06ced9bb8e7c3","datavalue":{"value":"structural complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q3489449$1A955DEE-2FBC-4315-9781-6A0E968819A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c06f0e53c6c5fbb7dd3a27c773a95e9573990cd","datavalue":{"value":"characterizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q3489449$702019E5-C68B-4EB6-8530-6F87FE22DE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0bc1cc50e8d4b517f651118878724606a4faacd","datavalue":{"value":"reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q3489449$BB44FD36-E7F5-414A-A1D6-AA8697586177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"572a0352dccc24a14152d8567a5e6b9d05e7c4f1","datavalue":{"value":"classes \\(\\Sigma ^ P_ k\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q3489449$A6129141-5EAF-4804-8B38-42831435F207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"319f7aef6d48907b019428ced327b73484cf6132","datavalue":{"value":"polynomial-time hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q3489449$3182D3FA-907A-4D2A-8B0D-C0BC0E657217","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":"Q3489449$7AF695DE-883E-486A-9126-8380503F3CAC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b9c0297ccc7943530d7e60dae41b7cff33d7166","datavalue":{"value":{"entity-type":"item","numeric-id":1106840,"id":"Q1106840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$EAD9E7D9-1EA7-4321-A2D8-0C66BD78A973","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3771f8171656e0aed45bf0777afe8aad7a3a9","datavalue":{"value":{"entity-type":"item","numeric-id":3902480,"id":"Q3902480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$25A94680-2BCD-4DFF-BFC8-9E79510A0D82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37c3ecf6bbb80d30a5d10d29d6b817116fc55217","datavalue":{"value":{"entity-type":"item","numeric-id":1061119,"id":"Q1061119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$E36BD237-25F8-48BD-BAC2-83D01A2B15F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9595afdcd6f0a34d637d70f3c89fca691c6293c","datavalue":{"value":{"entity-type":"item","numeric-id":3241504,"id":"Q3241504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$1CDCFC52-3C63-456A-A3DB-9ACE1DDD4EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f6b0479428e2ab3288ce6f4b559b16519ef8391","datavalue":{"value":{"entity-type":"item","numeric-id":5624436,"id":"Q5624436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$27264A49-640C-42DB-924F-7273E1D0C732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$7515FCF7-6AA7-44C4-A258-D90B65AA3178","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":"Q3489449$F3757FD9-16E0-4E43-A4ED-3747E4C6DDD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a098647e2133258d563151bef051aaad7f30f8b","datavalue":{"value":{"entity-type":"item","numeric-id":1055405,"id":"Q1055405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$837833B9-2C4F-478E-B702-E9A01D271A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b409306bdf364930adcbf624496cede43048b2af","datavalue":{"value":{"entity-type":"item","numeric-id":1337458,"id":"Q1337458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$9F3C3D2D-8E49-4D19-9E61-7E9AF266E804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82ec5ff11ebb3d616e28e195b227a685a32cbd40","datavalue":{"value":{"entity-type":"item","numeric-id":1124342,"id":"Q1124342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$F9F1A171-FE0F-45AC-8402-A9B0F167861B","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":"Q3489449$4585F83A-7830-47FC-BAAE-E086239CA244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cce5c439270a6cf81c822177c2a01f98c23f8e3","datavalue":{"value":{"entity-type":"item","numeric-id":2639849,"id":"Q2639849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$B1987664-5F83-4C1F-89BD-65D2DEAF9026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58caa984504f2a274575f62b4f30ecba0bce4643","datavalue":{"value":{"entity-type":"item","numeric-id":3835025,"id":"Q3835025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$5A047EF6-5989-4A0D-81A3-674C46E51583","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3065df023fcb2411980df376c6fc4777f5d291a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241440,"id":"Q1241440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3489449$9F49C8E5-D210-4698-80D3-F436721A6485","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"75ac596a7b6fc212e24983e48b4ba6de0a5f24a1","datavalue":{"value":"https://doi.org/10.1007/bf02090773","type":"string"},"datatype":"url"},"type":"statement","id":"Q3489449$70B7720D-3190-4248-A324-A83D735A645E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cdfa2a3fec1b5260191b246b601ed10d5f52ad92","datavalue":{"value":"W2019893603","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3489449$98BC50A7-8BB9-4888-8BAB-87D68CCBE357","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fee364ab53138fa2e01243baca3137d5cd0e544","datavalue":{"value":{"entity-type":"item","numeric-id":2366567,"id":"Q2366567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48590c440bf442162023c80ba8cd0953f5952ce1","datavalue":{"value":{"amount":"+0.8060195446014404","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":"Q3489449$E1A77DAC-66DD-449B-A633-88CD4330ED82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3673fe179748cd0a4b305cfea951b44bd4438b9","datavalue":{"value":{"entity-type":"item","numeric-id":3760533,"id":"Q3760533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b364570de94b8a250576d45a0acd4547ab7e7555","datavalue":{"value":{"amount":"+0.8057147860527039","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":"Q3489449$74C4F705-6E58-4E16-853C-A010F0972797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07a9d4ad7ae22f524bdc74d68af21286c7e889ee","datavalue":{"value":{"entity-type":"item","numeric-id":3763590,"id":"Q3763590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4b4722fe5473d13b89b2ea0be1d1912ce049d94","datavalue":{"value":{"amount":"+0.7885950207710266","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":"Q3489449$487E8F47-DFFD-4C21-B0AD-5BF74FACB2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b8dba0ee0b7fb52ecf33f781147252a02f5f572","datavalue":{"value":{"entity-type":"item","numeric-id":4298368,"id":"Q4298368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91c449642dcdc70a6727dcb682844dd6644be465","datavalue":{"value":{"amount":"+0.774770200252533","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":"Q3489449$CA90A18D-15A0-4528-BC87-22233C81BE1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b09f64724988c7a029e89b27b72c75acb7a8bf5","datavalue":{"value":{"entity-type":"item","numeric-id":3816983,"id":"Q3816983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0febacda87ac55b441f3b79b1f39832c9a0a625","datavalue":{"value":{"amount":"+0.7731913924217224","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":"Q3489449$360AC0C0-FFF7-4072-BB8C-E2F2CFC45AD3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3489449","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3489449"}}}}}