{"entities":{"Q657564":{"pageid":659413,"ns":120,"title":"Item:Q657564","lastrevid":51398096,"modified":"2026-01-18T02:08:04Z","type":"item","id":"Q657564","labels":{"en":{"language":"en","value":"Algorithmic relative complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5995950"}},"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":"Q657564$F02031C0-CE65-4F80-B376-B0A6F4354F47","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9f6c08abf0b44be4154a02cab2a940eda6d197e1","datavalue":{"value":{"text":"Algorithmic relative complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q657564$EC6330D8-9412-4BD1-A167-6EBD4523400C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f5f849c2ae499607532cdd211380efbe3448934c","datavalue":{"value":"1229.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q657564$D0FC15F0-6B31-4FAD-AFFB-297B28441F0B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"99f04b702f7ef93c6ba8e0433fff3b7d6371d849","datavalue":{"value":{"entity-type":"item","numeric-id":657562,"id":"Q657562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$641FF9D9-BACA-483F-9E13-DFB8953EB197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"748a6610b48ed3dee146eef0dcd28e4f6a70c5a4","datavalue":{"value":{"entity-type":"item","numeric-id":657563,"id":"Q657563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$F0CBED01-FDDA-45F5-8562-AE352913E160","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"5cd7699fb04f6d346a394454e45cb2ba8d87b719","datavalue":{"value":{"entity-type":"item","numeric-id":72504,"id":"Q72504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$0DE87704-C9A9-4455-B833-1CE62AD4D38C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e9607f48c18978638c077ebad91858c89c592748","datavalue":{"value":{"time":"+2012-01-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q657564$E2315909-D069-4061-B0BE-A3A0CC266666","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d8a7ead31c9d47f4e0da50dd55c8ac31a35410b3","datavalue":{"value":"Summary: Information content and compression are tightly related concepts that can be addressed through both classical and algorithmic information theories, on the basis of Shannon entropy and Kolmogorov complexity, respectively. The definition of several entities in Kolmogorov's framework relies upon ideas from classical information theory, and these two approaches share many common traits. In this work, we expand the relations between these two frameworks by introducing algorithmic cross-complexity and relative complexity, counterparts of the cross-entropy and relative entropy (or Kullback-Leibler divergence) found in Shannon's framework. We define the cross-complexity of an object \\(x\\) with respect to another object \\(y\\) as the amount of computational resources needed to specify \\(x\\) in terms of \\(y\\), and the complexity of \\(x\\) related to \\(y\\) as the compression power which is lost when adopting such a description for \\(x\\), compared to the shortest representation of \\(x\\). Properties of analogous quantities in classical information theory hold for these new concepts. As these notions are incomputable, a suitable approximation based upon data compression is derived to enable the application to real data, yielding a divergence measure applicable to any pair of strings. Example applications are outlined, involving authorship attribution and satellite image classification, as well as a comparison to similar established techniques.","type":"string"},"datatype":"string"},"type":"statement","id":"Q657564$B789B9DF-6AFA-4D22-AD69-C3D1D18AA93B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q657564$D33DA57A-5349-4F46-ADA3-3750A5C3AD1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q657564$E6E34D7B-7F51-4BB7-85C6-1EA912AFED1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e30d62051793251cdb7305d492b252b2239dfb5e","datavalue":{"value":"94A17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q657564$7A4AB1D3-AD98-4236-852F-FC0EE5D58358","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91e20f172539a33ca69e722ad7854a2e92ec334b","datavalue":{"value":"5995950","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q657564$AC99A7C5-E454-4ACF-94E1-86ECE308B621","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q657564$060F342C-F885-4D63-A432-B6C940A979D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4f8dd5c493bcfe457a2c05cd0b9ce65be151090","datavalue":{"value":"compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q657564$CC2D651A-2D2B-4C94-B88B-7EA20A939AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fed3e2333259b39b399a6b454958f41a7fbb24c","datavalue":{"value":"relative entropy","type":"string"},"datatype":"string"},"type":"statement","id":"Q657564$6042205C-8174-43CA-9B9D-82D10B4C48C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccc8672e06de051a8620d4f2e60c781a4dd838e7","datavalue":{"value":"Kullback-Leibler divergence","type":"string"},"datatype":"string"},"type":"statement","id":"Q657564$1592888D-30A3-4AED-8AAE-0EBC6C9E4311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3795e9ead47e9567cc39be3aa30c2e668fdfcd2d","datavalue":{"value":"similarity measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q657564$712443A9-6BCB-4D75-A752-37CA57649341","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3fae2bae253fcdbb80aae59b70c44d9baa8e1398","datavalue":{"value":"compression based distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q657564$CBD52AFC-3A81-4E17-A747-087A520810DE","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":"Q657564$9AA351DE-1C68-4408-9241-9FED9ABF32C5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f73cabe10353dbdc96b8a467b2d958820b0ce9d6","datavalue":{"value":"https://doi.org/10.3390/e13040902","type":"string"},"datatype":"url"},"type":"statement","id":"Q657564$8033B8FB-7CC2-494E-96DF-6750F72EEAA9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d3afb84c8e04d4523c96cb2de06d515446b8cec9","datavalue":{"value":"W2095699593","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q657564$6101BF64-8FA8-4DC1-AA71-4C3D4CD16EEE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"78f0cf2b8270f6087b7bc3862da42dbac9e1bf1f","datavalue":{"value":{"entity-type":"item","numeric-id":88168,"id":"Q88168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$BF708B0D-1AEB-4572-8553-480D95DC1D04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ad1299f57f214c4c9659c7db19e25c6d0461799","datavalue":{"value":{"entity-type":"item","numeric-id":5900062,"id":"Q5900062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$0BBEDCD0-B1B5-474A-8740-8BE70DB794D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57424f9c7401f189cbc651a0426fed38012be235","datavalue":{"value":{"entity-type":"item","numeric-id":3547244,"id":"Q3547244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$23713ABC-8F5E-40E4-8ADB-04F19B8A48F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01673f5c74e4eb89b296e605ee9a6ebb81d8ecb1","datavalue":{"value":{"entity-type":"item","numeric-id":4307329,"id":"Q4307329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$8EA7EC5D-0B2A-4AC2-93DD-BFA8B37F645B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9d022149ece595446a9644635af062a930e4f1b","datavalue":{"value":{"entity-type":"item","numeric-id":5674429,"id":"Q5674429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$419C9354-2F46-4D19-96FD-BDDF5A2891E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4673e71a7d4faf27e474d74b82d0985b6024b624","datavalue":{"value":{"entity-type":"item","numeric-id":5558743,"id":"Q5558743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$6E1C76AD-BEB4-4F65-ADA6-9A85A029F89C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d88a1af1ba4970e30cf9005409b23a741c859fe","datavalue":{"value":{"entity-type":"item","numeric-id":5579041,"id":"Q5579041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$DB7CE5A0-7B5E-453C-A757-618CFE3B867D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d704ba9c4893ee9e94158bb0f650b625582e5218","datavalue":{"value":{"entity-type":"item","numeric-id":5281412,"id":"Q5281412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$907BCE8B-59F6-4DC6-AF1E-9A4566E7C2A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dacfd5dac4a957847b8c3c48ad2905e27ee4cee","datavalue":{"value":{"entity-type":"item","numeric-id":3546694,"id":"Q3546694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$C9745696-01A7-44CB-A98D-B6142BAC69E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b0a309745c64acb47841d6e624171f61a9cfed","datavalue":{"value":{"entity-type":"item","numeric-id":3546722,"id":"Q3546722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$0BC89E92-0985-45F2-B589-4FFC106F95F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50d120594022b5cf80cf75d47d29ef8d6bd81a47","datavalue":{"value":{"entity-type":"item","numeric-id":5804592,"id":"Q5804592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$3E1039E9-8A49-4E29-923D-99D88CA9B815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90020d6693b03e8738122b57ca028c93d461c6c8","datavalue":{"value":{"entity-type":"item","numeric-id":4457477,"id":"Q4457477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$E35523DF-2EDB-49BE-9C89-C90819BB4960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fdf95025d799669e3421910acfe81785019f1fc","datavalue":{"value":{"entity-type":"item","numeric-id":3398488,"id":"Q3398488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q657564$74CDBB76-2450-4303-A6AA-ABEC88B3E5A0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f7888c106b93c4cc302d2b8e6eeb8637ead99520","datavalue":{"value":"10.3390/E13040902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q657564$1A9C932E-E46A-4A18-A0E2-5FA5ABCB806B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e33c062fd7adc8943a64038679252b6c43844973","datavalue":{"value":{"entity-type":"item","numeric-id":2122124,"id":"Q2122124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6417cbee40f5c30e1702077fd0a681b3c386840f","datavalue":{"value":{"amount":"+0.7585341930389404","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":"Q657564$13FF1097-87FD-4B18-9BF6-4C606D7F33FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"988bef0338afe20cbd975aa2773a4e7c6770453e","datavalue":{"value":{"entity-type":"item","numeric-id":5250215,"id":"Q5250215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbc2b508dfc0960084fc577155bb290de2b8f449","datavalue":{"value":{"amount":"+0.7538870573043823","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":"Q657564$E365DA45-EE9D-4FD2-AEAA-9C4D10E6C740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"882c5bd5df4243e428b7cfd842f9bf3204f45728","datavalue":{"value":{"entity-type":"item","numeric-id":4473230,"id":"Q4473230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87dd21edd7fd421d5bab3a3892b00d60a0efbae6","datavalue":{"value":{"amount":"+0.7486543655395508","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":"Q657564$13014992-4323-4886-AA60-0C2708F6EAEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c62a3fcd898c85fb63c3bca3d5ea46f78c660cd","datavalue":{"value":{"entity-type":"item","numeric-id":4701113,"id":"Q4701113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dcaeb71627a78e752ba5df624fbd21b7bdfcdd8","datavalue":{"value":{"amount":"+0.7441626787185669","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":"Q657564$481894DE-35AB-461E-8875-6E22BAAB50A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41b6614744de0e7fb11ae10d771662867793ca66","datavalue":{"value":{"entity-type":"item","numeric-id":2973062,"id":"Q2973062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dcaeb71627a78e752ba5df624fbd21b7bdfcdd8","datavalue":{"value":{"amount":"+0.7441626787185669","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":"Q657564$D7841270-84E8-4068-9611-E41A79DB4BEE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:657564","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:657564"}}}}}