{"entities":{"Q1198047":{"pageid":1208796,"ns":120,"title":"Item:Q1198047","lastrevid":66847191,"modified":"2026-04-12T13:15:24Z","type":"item","id":"Q1198047","labels":{"en":{"language":"en","value":"Average case complexity under the universal distribution equals worst- case complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92108"}},"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":"Q1198047$7168BE7D-FD8C-49DB-83F6-A506C72879F9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"43968e75d549c31a9f34353ac06e04a203b01580","datavalue":{"value":{"text":"Average case complexity under the universal distribution equals worst- case complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1198047$B4EE8EC8-42AC-4D36-8069-0E13FC27B4CF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"989faf7ac43851f7d62e98075fe00569850e40fb","datavalue":{"value":"0780.68064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198047$F7D9694A-2E01-4D29-89FE-968C7E901989","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"73682c19f33bb30adbd1eca0047a34cf9f0e9a8b","datavalue":{"value":"10.1016/0020-0190(92)90138-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198047$7E26C76D-F8DD-4A6D-98FF-6531D8779B2F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e666d41882411f9ee5a3d11cf0ad33cabba8b2","datavalue":{"value":{"entity-type":"item","numeric-id":672057,"id":"Q672057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198047$8BB3E7EB-71BD-4F21-8DD3-8F69F6A95ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"60b2337bc50810374b4ca0c66cb11407509a5fbe","datavalue":{"value":{"entity-type":"item","numeric-id":354146,"id":"Q354146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198047$2C28B002-8ADD-48F0-9E33-B36D498A1CD1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198047$F011D721-252F-42CE-BF83-234D38277507","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1198047$1B17EE2C-89E9-407E-8EC0-63B9362FDC62","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198047$CEC9EA13-F07A-4BA9-BEF3-C346E4495CE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198047$F33F71CC-0E83-4F32-AA05-54854C8D6717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198047$54625BC6-90C4-4519-B7BF-6E9D362DB29B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83834358dad9813aa87d6d79d912d0652b4c5ee7","datavalue":{"value":"92108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1198047$D17946C3-3312-4ADB-B5C1-EC413DC46BE0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$0ADB5566-0539-4994-BC3B-CD956978DBA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$6D5076F3-AC19-4702-8B1B-9C72085A292D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15f48ed4787baedea8f978808eba84ed180892c1","datavalue":{"value":"uniform distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$73C98FD3-F0FA-4E5E-8BD6-387D93500EE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbea74bea78fb379c705a66bfbc4d6cf8cdd3408","datavalue":{"value":"quicksort","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$BCC89183-71E0-4F62-B724-40D75524C875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65ab92e7120d95ac7c64ac8046b94df35ee34228","datavalue":{"value":"average NP completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$133A1BF7-D863-434E-A3B1-372A2FFDFCB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f5be192625e7ec06f60848bf5fa4300b42d88bc","datavalue":{"value":"average complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$6BF0848A-8B96-4D44-B196-EA5A7B477F33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8f7bbc4dfe445636dcfa277be31f8fcb4662d5d","datavalue":{"value":"universal distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$5C90F534-BBE6-4B32-9000-239EDAE92801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83b6378c1e09396d02149d7bb0f655a81bd78a34","datavalue":{"value":"worst-case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$596EED0B-A435-4BEF-BF27-A618955816B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$84C34B19-5D61-47C2-A6DE-D8C439B8644F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fc59007b2b1960a263350309435ca1e06e896b5","datavalue":{"value":"space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$D0306AE1-FF8D-45DA-A5C0-1280997987E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f11a697ca4320b2c5e334107aae45a37f7f8f8b","datavalue":{"value":"sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1198047$5597EA61-6DE4-40BA-A25F-AB486DCA91CA","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":"Q1198047$C6326B2B-CE58-485D-AF5A-009AAA86C149","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"02bac57d5a29434e0c004e82620bedf9a6096d9b","datavalue":{"value":{"entity-type":"item","numeric-id":4074808,"id":"Q4074808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198047$A0B33CD3-7D0B-44A7-A490-7D8C3DF01501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04533b5e4f54e7a61c4fc1c55a4a47c19e20f43a","datavalue":{"value":{"entity-type":"item","numeric-id":3718151,"id":"Q3718151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198047$1D7FB9BC-74BA-433E-A089-473D90E98737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"accb3332cc2099d0b2a0ffd4c035aeea89f6722c","datavalue":{"value":{"entity-type":"item","numeric-id":4385509,"id":"Q4385509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198047$5E69580A-C21B-4529-90B0-5A74B680E8AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6c50777e5961226fad33fc5b9491156664a3e6f","datavalue":{"value":{"entity-type":"item","numeric-id":5674994,"id":"Q5674994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198047$9F909CBE-4815-4C9E-8C9D-5AAEECF8C4E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55cfc0ff9590d7beb1ccb038cddeb12787b6740f","datavalue":{"value":{"entity-type":"item","numeric-id":5626617,"id":"Q5626617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1198047$0A7AF9DE-C132-4A5D-A4D3-03C513E466D8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea2c7d667c894fb7c8bf4f1a93d55b7f236ea2db","datavalue":{"value":{"entity-type":"item","numeric-id":4336271,"id":"Q4336271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c9b0e4d5892b734e6c75463149f3ceffc573353","datavalue":{"value":{"amount":"+0.8526324033737183","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":"Q1198047$368A4CFF-CEDD-49EE-BD70-18A8325DB5F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ae14f460039962e32710c4bf9141958f43bba35","datavalue":{"value":{"entity-type":"item","numeric-id":1190984,"id":"Q1190984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52ecc36d4b8aa104b9fe3cbf0f4757a91680feb4","datavalue":{"value":{"amount":"+0.800040066242218","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":"Q1198047$7E1B7069-D3CB-438E-9C49-27FAD656D97E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42d193da47e6938bf321ec935dfe5ccdfc55130f","datavalue":{"value":{"entity-type":"item","numeric-id":1916530,"id":"Q1916530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85510a8939768b0442aad0dd7c35c7518a2d64ae","datavalue":{"value":{"amount":"+0.7993965744972229","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":"Q1198047$36FD7997-A4BF-4BE5-B790-BC4705A40CE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ec053189c639563ca46dd12436adebaac1fb118","datavalue":{"value":{"entity-type":"item","numeric-id":1587331,"id":"Q1587331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82a5395a0006b0a0683c55aade6f5870d223ea9a","datavalue":{"value":{"amount":"+0.7975180745124817","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":"Q1198047$1F5843A3-E056-4305-B309-013C10FC399E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54254a285e825cd4b7f4d25c73c6088f85d8abc4","datavalue":{"value":{"entity-type":"item","numeric-id":4281567,"id":"Q4281567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c286f65348cbfd13c805ecbb65fbf7120710c3c7","datavalue":{"value":{"amount":"+0.7965726852416992","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":"Q1198047$0C80F997-9C64-4C0E-B843-186ED163F38A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Average case complexity under the universal distribution equals worst- case complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Average_case_complexity_under_the_universal_distribution_equals_worst-_case_complexity"}}}}}