{"entities":{"Q2475580":{"pageid":2486323,"ns":120,"title":"Item:Q2475580","lastrevid":56852958,"modified":"2026-03-23T20:03:44Z","type":"item","id":"Q2475580","labels":{"en":{"language":"en","value":"If NP languages are hard on the worst-case, then it is easy to find their hard instances"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5247539"}},"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":"Q2475580$F9719CD9-9B2A-42E7-B3FA-AA46702C5AA7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f5ccea4a40c1749e96ad5357fff2a17305ea0f79","datavalue":{"value":{"text":"If NP languages are hard on the worst-case, then it is easy to find their hard instances","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2475580$D2BD0499-8D5D-4281-BB7F-B06439F0900F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8d1a99565272ca2860919194bf8917f2ca16f4ae","datavalue":{"value":"1133.68352","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475580$4587F258-3FE1-4CDD-950E-E897256E8524","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7b4613bd8d21f7044c60802c77e4d238e7f545e4","datavalue":{"value":{"entity-type":"item","numeric-id":374167,"id":"Q374167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475580$DCF6BBAE-FF76-42C8-B86C-57B632461F09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"256705a197690b134d5b3e203b26d7eb8b836aa7","datavalue":{"value":{"entity-type":"item","numeric-id":301522,"id":"Q301522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475580$6373F4FF-1CDB-4CFC-A4DE-49B388A68597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6fce015a1448257e1b51552202e3fc2be212616","datavalue":{"value":{"entity-type":"item","numeric-id":764352,"id":"Q764352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475580$655DC73D-2901-4391-8790-AB4678445ACB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475580$29DD55CD-2C60-4885-AB5B-DE5BF4B2E10F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c5191b06fb6cb88c011afaa0f154255cfe3a8de0","datavalue":{"value":{"time":"+2008-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2475580$0F58D2E9-8932-4B53-88C8-C54A6EDA9A74","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475580$F89CEA6E-1E1E-4EAF-B9C9-2B8AF204C657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475580$23281905-9253-4C31-8766-14528D6B9E04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475580$65145750-BAA8-4BB6-9EA1-E174F985CF01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475580$9BFA5074-2619-4C45-8FDD-7BA10AF4EAF7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd068b9779a41d856ee64d3379e298a446390681","datavalue":{"value":"5247539","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475580$C5263579-003B-43F6-A3E5-34961DE4AD59","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09559db9d62bdeb85ec48252d0645cc58e03df6e","datavalue":{"value":"Average-case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475580$C1C6AC29-9895-4EDC-9135-A31996614AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5867a69c0aef7e25914abe709e5ac3be97b953db","datavalue":{"value":"worst-case to average-case reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475580$E3A0FA3E-9537-4AA1-8BA9-E2B8D16B50FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af5dcef2f003e2951514f8eddd6da839c9ce6049","datavalue":{"value":"foundations of cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475580$50CC35D8-20C9-4714-9A4F-EFFBDA1FF4F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd974d85f1693afdcfd121d4e1a0a187d7798320","datavalue":{"value":"pseudo classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q2475580$DA70B2C7-64D7-4D79-99EF-9206B4B43DD0","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"36b70c01c1456faf6ed468703467a20d61b41589","datavalue":{"value":"Q62398467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475580$24089417-A4FE-48B1-96CF-9CD54B26E0F6","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":"Q2475580$705752DE-C309-4A32-B4DC-C9E57BCA7C9A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f01ba5ae610870499862c824adc03b009c50036f","datavalue":{"value":"https://doi.org/10.1007/s00037-007-0235-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q2475580$A83AB494-47DE-43AD-950A-D2ABC7535768","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"60677ba8b8e313bd2f1066dceaf82ded897ca46b","datavalue":{"value":"W2163083173","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475580$AC843B18-F2D7-4C99-B228-7019C718B472","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c7aa494cbdb3731a06826dcb5eff438b8b829fc0","datavalue":{"value":"10.1007/S00037-007-0235-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2475580$59ECDB0F-3853-4441-B5CB-A3FD96E04BB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a6cc3daf94eb26e21834aa7325478cabd372985","datavalue":{"value":{"entity-type":"item","numeric-id":5757460,"id":"Q5757460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deefe8671c1d4c90fb8217cba54cae3a7bd8c4c5","datavalue":{"value":{"amount":"+0.860987663269043","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":"Q2475580$01431253-A0AC-4333-9866-33A43716D846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87a625c86e9c9c64ed2c3e0978f92464db40a07e","datavalue":{"value":{"entity-type":"item","numeric-id":3603494,"id":"Q3603494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e7c51b116b430314ba7e8c34ec21f0cdcee53b6","datavalue":{"value":{"amount":"+0.8591562509536743","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":"Q2475580$9FB0A13F-7D4C-4B9C-847A-7F30F575DD63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfd2ae05e16f02581b8df0456f81c8bd31442fae","datavalue":{"value":{"entity-type":"item","numeric-id":4928485,"id":"Q4928485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"547f936c0346396f156c35b05dbff672c707e46d","datavalue":{"value":{"amount":"+0.8587364554405212","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":"Q2475580$B9848B1A-1909-4559-99A6-F1F2E81DF155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b3d87c217443bfa0282780a97ff94e4d17c2e71","datavalue":{"value":{"entity-type":"item","numeric-id":3413362,"id":"Q3413362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6dc50cc6c93f870f4effec914f6538e06ee2d0db","datavalue":{"value":{"amount":"+0.8462793231010437","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":"Q2475580$F3C15194-5390-44AF-9230-284A310AC741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"962942437eb5c00c77f37487e8038dd7faccea60","datavalue":{"value":{"entity-type":"item","numeric-id":5901182,"id":"Q5901182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dffabb48298ce56b927895ad2b9da339e6343b5","datavalue":{"value":{"amount":"+0.8383603692054749","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":"Q2475580$AB3661F2-5D76-4297-83E5-C41E0A0E5687","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"bee1ddd2bb542a0e64ca96574e4fab1bba361385","datavalue":{"value":{"entity-type":"item","numeric-id":57074,"id":"Q57074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2475580$301A0611-CDA7-41B4-A181-A3E3E3B199C3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2475580","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2475580"}}}}}