{"entities":{"Q6568358":{"pageid":14179513,"ns":120,"title":"Item:Q6568358","lastrevid":99822701,"modified":"2026-06-05T20:47:02Z","type":"item","id":"Q6568358","labels":{"en":{"language":"en","value":"Probabilistic Kolmogorov complexity with applications to average-case complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7877663"}},"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":"Q6568358$2D39A304-36D5-4801-900B-5D226870DF32","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"34a258d9efe8384a55877a8b8df8e9c54ee589f8","datavalue":{"value":{"text":"Probabilistic Kolmogorov complexity with applications to average-case complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6568358$1CAC2F50-3EB9-4BA5-A302-28E945ABBCFB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f5c1ca6fbb83c022439b0ad385758666d0ad472","datavalue":{"value":{"entity-type":"item","numeric-id":6568357,"id":"Q6568357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6568358$87A820C0-0039-4226-B68F-1E3C70861641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0d2539da0629477438d7ce1d3087216415362d1","datavalue":{"value":{"entity-type":"item","numeric-id":230568,"id":"Q230568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6568358$16AB3CEF-C097-434F-BF03-186B14AD4968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9f670497f3128c3a7e93dacf82b05360aa0f11f5","datavalue":{"value":{"entity-type":"item","numeric-id":4978007,"id":"Q4978007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6568358$47C67710-A02F-4E9D-A88A-AED569F945D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7805073a5ae9040c991641317a6d3bbe630dcf22","datavalue":{"value":{"entity-type":"item","numeric-id":2125079,"id":"Q2125079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6568358$06225E39-9096-419B-B3BC-35BA7A3F7D79","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"df053448a65992a80a8bb9dc3531ec74f75059c3","datavalue":{"value":{"time":"+2024-07-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6568358$85615CE6-AFF1-456D-ACCF-7B8AAA786D31","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6568358$9C921411-6FF5-4885-ABBD-670EE275D9BE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f3fea6f2f499507d87d345fb5eb47d13b291a9c5","datavalue":{"value":"7877663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6568358$C27240EC-F4F8-432A-A580-5A38645BF315","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eeb5cf5222b6371fb7f9c168c78eb205663c9be7","datavalue":{"value":"average-case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6568358$56AE7CD5-1171-45C3-B3A6-676C55605BD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6568358$6141F9EA-4367-4F41-AACF-158C4B77C90D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"094a4c4b135f1ae2b5a83b41dcaeeeed2c55f7e9","datavalue":{"value":"meta-complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6568358$2D9F2D38-04CE-4804-A50E-90829F162B23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5867a69c0aef7e25914abe709e5ac3be97b953db","datavalue":{"value":"worst-case to average-case reductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q6568358$BE85746A-8776-463B-9DCF-F6486173FDF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05ca76faeb672415cff41bbc3ad8454e227be1fa","datavalue":{"value":"learning","type":"string"},"datatype":"string"},"type":"statement","id":"Q6568358$684A349A-97A6-4F95-806F-5C1C0C78EB70","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":"Q6568358$3EF605D6-1C99-43CB-9AAA-DBE3836D610D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"032ef8ab4dd3117b3b9848d359ad31b9fbb71801","datavalue":{"value":"10.4230/LIPICS.CCC.2022.16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6568358$A30C208F-6332-413A-8310-EC28A1AB32F7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Probabilistic Kolmogorov complexity with applications to average-case complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Probabilistic_Kolmogorov_complexity_with_applications_to_average-case_complexity"}}}}}