{"entities":{"Q1119389":{"pageid":1130138,"ns":120,"title":"Item:Q1119389","lastrevid":66339438,"modified":"2026-04-12T09:26:27Z","type":"item","id":"Q1119389","labels":{"en":{"language":"en","value":"Notes on polynomial levelability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4098713"}},"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":"Q1119389$CBC43527-00A5-40D1-AF9E-F346489DD813","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b026eb736cfc7bee54f58e108cd0e810cab1bfaf","datavalue":{"value":{"text":"Notes on polynomial levelability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1119389$33B4EB27-3D8C-498C-9445-D0B10D45D133","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b150fc050d9049442d38fadff33abfeb1cf416b4","datavalue":{"value":"0671.68011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119389$4EEDC900-E593-4C35-BD97-5D446DAE27E6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9ee83adf210a4626408b5cff3a58ee47e1ea9fd4","datavalue":{"value":"10.1007/BF02006060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119389$A188C0F2-2157-42C9-ABB7-BF17193EB0B4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bd8a7678534b4c4a434a737b8e34eefad997d7a4","datavalue":{"value":{"entity-type":"item","numeric-id":176689,"id":"Q176689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119389$B9B50071-65D5-43F0-9E79-C0BE019C22F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1119389$432606C4-5915-4BA9-8DF1-8A5A1D369EC5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f5c75fe83bb83d982b6d02bc98525a487ac6dd9e","datavalue":{"value":"The author addresses the question whether certain types of approximation algorithms for intractable problems admit certain speed-up phenomena. It is shown that invertibly paddable sets as well complete sets for EXPTIME do have such speed-up properties.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119389$77E8BCB0-ADB2-4781-91F1-DE357418B53F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119389$4871F39E-2D6F-47F0-AE83-E7D9032018F7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ee6e81edbe8b0efa680de9dfc367239ae7bc67c","datavalue":{"value":"4098713","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119389$A20DAB73-F56D-4BC6-B4BD-71AB16DBF3D8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9df740b318dccdf0a655dcae33c38cfaefe2d926","datavalue":{"value":"polynomial levelability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119389$C139E060-0BE7-4047-9978-CF4795007E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119389$53D72ABB-3F5C-4CD2-BC72-7089ECB686F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2d176dcf8014bfec2c4899579ee7ce9e18294338","datavalue":{"value":{"entity-type":"item","numeric-id":166203,"id":"Q166203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119389$650D3A71-341E-4262-BFD5-EB4E38037AC3","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":"Q1119389$B982689D-F7A3-4EA2-971A-F465856BCD52","rank":"normal"}],"P223":[{"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":"Q1119389$9511714A-A114-471D-9632-6373D1167DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cd3656cf316bb6b47d075cb851e6ca065390824","datavalue":{"value":{"entity-type":"item","numeric-id":3051374,"id":"Q3051374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119389$695E88BA-9B4F-45E5-A44F-D43EA24F9AAE","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":"Q1119389$DD6A217D-F8F1-4621-9725-61DC369B562C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbb02b99e27c5e54617516f488ff23a36459dc0b","datavalue":{"value":{"entity-type":"item","numeric-id":3711750,"id":"Q3711750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119389$AD7D4C16-7A3C-4D2B-A9DD-76B3028A8553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6139d2fb76790fbc1a2ff20446f11785d8f1488","datavalue":{"value":{"entity-type":"item","numeric-id":1168733,"id":"Q1168733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119389$8C147424-5E5F-49B4-AFF9-24E5B0A443BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01fc2040ffe16ed03fdd5700cb1de1e73a3cea54","datavalue":{"value":{"entity-type":"item","numeric-id":3787474,"id":"Q3787474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119389$690B19A0-47BB-4698-B9DE-B4E7CD45631B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84057446059926ea88bd26626fcfa1fd37a11f8d","datavalue":{"value":{"entity-type":"item","numeric-id":4727430,"id":"Q4727430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119389$F0B610B2-559C-42E8-A5A3-584611F58E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f17a7f319117d5a44769bf519f74a5e5ddbffa2f","datavalue":{"value":{"entity-type":"item","numeric-id":1068536,"id":"Q1068536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119389$04AF7D36-439D-41C3-8CA1-98B8EE4D1849","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a6cda79edbd7844280d7256f6bebd6ec8725739","datavalue":{"value":{"entity-type":"item","numeric-id":3335768,"id":"Q3335768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119389$7FD1D6F1-E6D2-47F3-8211-D016966060FB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c8ef21635b9ac2885ea7ad950796f414cf8a22c","datavalue":{"value":{"entity-type":"item","numeric-id":3787474,"id":"Q3787474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e340e16fae87f4477d6f3f5cb76becb8212af6ee","datavalue":{"value":{"amount":"+0.81790691614151","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":"Q1119389$CB3C6D11-8852-4514-94AA-25B57AFD21EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5be36c92a7f258aa1a4283696fc8484cac4a14ee","datavalue":{"value":{"entity-type":"item","numeric-id":5096868,"id":"Q5096868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c47a948c533443dc3d5342b68714dd63be52f2b9","datavalue":{"value":{"amount":"+0.7830540537834167","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":"Q1119389$B434A5C8-DC77-48D8-A567-252E670FDC91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6c07449b1a3d844de5f6dbe6b57ce0296d627c2","datavalue":{"value":{"entity-type":"item","numeric-id":3690221,"id":"Q3690221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2d3f8353a68481531b76e139095bec4700e96a0","datavalue":{"value":{"amount":"+0.7748448848724365","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":"Q1119389$F309D1F3-2A41-4C3D-A0F3-8AEA71E304FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76bee86aad2e013acc19ade9e2bd537ce83a0baa","datavalue":{"value":{"entity-type":"item","numeric-id":4027860,"id":"Q4027860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"704cb4c7943654071ea4af5052a53668516af346","datavalue":{"value":{"amount":"+0.7729704976081848","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":"Q1119389$002D8B76-565E-40D5-B228-AA90F77FAEB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"258391097cd9d2a06dd348da12c434a5fbb4fc6e","datavalue":{"value":{"entity-type":"item","numeric-id":3348409,"id":"Q3348409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64b081e92b979e0ff66f9e270deef78ea308b744","datavalue":{"value":{"amount":"+0.7700229287147522","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":"Q1119389$34D006FB-CDB7-4F55-81C8-1223E5A3BF1B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Notes on polynomial levelability","badges":[]}}}}}