{"entities":{"Q804291":{"pageid":806139,"ns":120,"title":"Item:Q804291","lastrevid":64504596,"modified":"2026-04-11T20:19:57Z","type":"item","id":"Q804291","labels":{"en":{"language":"en","value":"Kolmogorov characterizations of complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4201620"}},"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":"Q804291$B017469A-D836-41DF-99F7-312216D22278","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d8c2857a7c3fa1118410b09c99ed7e7c75eee89a","datavalue":{"value":{"text":"Kolmogorov characterizations of complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q804291$9FD8CDE0-AEF2-421D-BC5F-B46B98A26A5F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bdff87f8b82ef885d3a08f904e6c45d70040323e","datavalue":{"value":"0727.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804291$36F53474-BBB5-4AB0-ADD9-56F6570A559B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2a12f0b36550ba8c560c913f30aa7fad8eb50131","datavalue":{"value":"10.1016/0304-3975(91)90282-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804291$547F8BF2-37F3-4B47-B4FF-CDE872103D32","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d19271338ab1f986510acb204ee362887c758de3","datavalue":{"value":{"entity-type":"item","numeric-id":751269,"id":"Q751269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$81D867B4-15D9-47D2-A737-24E0CF47AEC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95d207a16ce6533a2e03f4685944467ead41f45c","datavalue":{"value":{"entity-type":"item","numeric-id":161382,"id":"Q161382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$D64EBC43-6D53-4991-A510-648F7CEDD5FD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$2779CD69-1F0A-4423-BC41-2DC966C56D8B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q804291$6BE18716-45F1-4F08-A276-6C65547F40CA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"36f093587e4515f0e0a6e0c773d2adbde92da1a6","datavalue":{"value":"The paper uses the notion of (resource-bounded) Kolmogorov-complexity to characterize the classes \\(\\Theta_ k^ p=P(\\Sigma_ k^ p)\\)- with logarithmically many queries to the oracle. The notion of pronouncements (query answer) of an oracle machine is introduced. Its Kolmogorov complexity determines whether classes of the polynomial-time hierarchy collapse.","type":"string"},"datatype":"string"},"type":"statement","id":"Q804291$2A77D85C-BB20-4867-8238-4C1A7A35352F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804291$91C3A8F2-C29E-47C4-AE64-3CA9FCF26807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804291$CF2DB810-1CB7-4148-9974-0EA7B9CC21C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804291$34BF6FF3-4A6F-42DB-8FFB-34FA11CB1B0B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ad88b0a6b0f2126a50634c3cababd9c13754070f","datavalue":{"value":"4201620","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804291$B037DA8F-0F29-46DC-9D00-26517DD9BE1B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"154ea0589dca3b50bef0f626c64f0e117c0eb521","datavalue":{"value":"polynomial hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q804291$EDD711AB-BD41-432F-B8C2-2465904316EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q804291$A6D55E0D-9E2F-4DF6-85E0-C0D7ECE58DF8","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":"Q804291$40F0D17E-8796-4BEE-BA39-1CD29E422786","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b50214b754b8bfe382fe51ec055c409971791932","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90282-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q804291$EB8A9A58-C8AF-4364-A7E6-E0F431359B34","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"841e77dfed4ee8ae0df850ae470f07cbb7b58409","datavalue":{"value":"W1989364208","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804291$D92C6521-31ED-4BCE-B80A-E8FC2C4B49B8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8e8c30651594c1eb9c8a2e2ed6c4a6e32cf1c7f","datavalue":{"value":{"entity-type":"item","numeric-id":4732106,"id":"Q4732106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$EDFB5F43-903E-46AD-9CA7-4A4945B8AEB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84014cdf26366752425810fb60975d784e8d2f3b","datavalue":{"value":{"entity-type":"item","numeric-id":751270,"id":"Q751270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$9EB76918-2E82-4C5E-A5DA-7B5E22B0E055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"486673ceaea3791821750647cd986822d2610503","datavalue":{"value":{"entity-type":"item","numeric-id":5750401,"id":"Q5750401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$9018CD24-1495-4DAE-80DF-DE4C37B2AB38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$E290720B-4A92-4BF3-A26F-AB0DCD33DFA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$36AE8082-881F-473A-947B-DF0CE71734F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd07bc9a9b69ce8a80cf38ac60dbedf570ebf67d","datavalue":{"value":{"entity-type":"item","numeric-id":1109566,"id":"Q1109566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$ABC32490-CB60-4690-B111-D04C27C2E354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91437bc3f5649edc6a7acb3095e2cdec844eb2e9","datavalue":{"value":{"entity-type":"item","numeric-id":3711749,"id":"Q3711749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$FC2D3E03-55C9-46D7-9DA1-672BBE888FEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a9b11ce25ed3d5901efe104d645aac38752039a","datavalue":{"value":{"entity-type":"item","numeric-id":3805899,"id":"Q3805899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$30B0C800-F403-46AB-BFA8-D7AB76037FED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80da5dbf79d1c137536de30a44e307449b537460","datavalue":{"value":{"entity-type":"item","numeric-id":584250,"id":"Q584250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$DB32D7DF-5F25-4997-838B-B9DBD392AE79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb9e97bb808371a3a6d9a49a0700ca457fcb589c","datavalue":{"value":{"entity-type":"item","numeric-id":908700,"id":"Q908700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$186A58CE-8842-4343-9119-F895604D04C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30f6e432ce9e9ae75031144ac1199e0b83ca0d7","datavalue":{"value":{"entity-type":"item","numeric-id":1107309,"id":"Q1107309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$BB573B60-C412-4FB5-BF86-838DDE3198A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa95955764545a75023f8016a50f24d28c32a007","datavalue":{"value":{"entity-type":"item","numeric-id":3815511,"id":"Q3815511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$7C13229C-F580-4924-898C-4D1592C305D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c62de5048fa954af00b82660416a315c8b87034","datavalue":{"value":{"entity-type":"item","numeric-id":1164997,"id":"Q1164997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$5981B456-4052-425D-A0F9-07433AF4A491","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":"Q804291$30B75EDD-0050-4324-AC0B-7F42E9382921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53e31dd483387e2770ec0ec431458678950cd036","datavalue":{"value":{"entity-type":"item","numeric-id":4743737,"id":"Q4743737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$8ED79FCC-9923-4B85-851D-F99D039AB3BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44ff2c269b97a88de0fe652e2add75347876b7e3","datavalue":{"value":{"entity-type":"item","numeric-id":1361890,"id":"Q1361890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$A28442F4-F73E-48F0-9497-27647DEB014C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14efb49139bf6636efc61d26092213d1072148b8","datavalue":{"value":{"entity-type":"item","numeric-id":4779250,"id":"Q4779250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$4A8459AA-0492-487C-AAEE-E140CEE2522B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3fdeac57e6ae30181fb2db5f7f4e10e134e5670","datavalue":{"value":{"entity-type":"item","numeric-id":1232181,"id":"Q1232181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$1A9F5D31-CF65-42FF-A30C-52A2062C922B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e27d3aece7f785e3af1e27802aac2c3e9fdc1ca","datavalue":{"value":{"entity-type":"item","numeric-id":5285980,"id":"Q5285980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6547023cd793781fb79ff5336e0aa072acb975f1","datavalue":{"value":{"amount":"+0.797208845615387","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":"Q804291$C92384BB-2926-484E-9281-31BE5B964804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49f7d9a0399ffd33d98baa6125f1cd87cb125d80","datavalue":{"value":{"entity-type":"item","numeric-id":5285981,"id":"Q5285981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bde60dbc6240a780326486deaf1114f70d7a8a13","datavalue":{"value":{"amount":"+0.7972086071968079","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":"Q804291$0DE9789D-36EC-41C2-ACD5-6CA044DF47F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9b5749abbe4b1319e1c11ae954ea5b10518adf9","datavalue":{"value":{"entity-type":"item","numeric-id":4023359,"id":"Q4023359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10478eff3a124ddd869cc9a02f1cadabcf462d87","datavalue":{"value":{"amount":"+0.7938534617424011","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":"Q804291$CF403704-341C-48DA-A431-3BBB73871F6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"858c2762706db7d04479573b979ade5052eeebdc","datavalue":{"value":{"entity-type":"item","numeric-id":3220570,"id":"Q3220570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2fa1123fb5e03bdc7c943ad45acb4b81056dfa0","datavalue":{"value":{"amount":"+0.7913133502006531","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":"Q804291$20236888-8B1A-4F3E-A628-C388B09412C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e4369555973b75271f5ec601224657a67aa409d","datavalue":{"value":{"entity-type":"item","numeric-id":5096790,"id":"Q5096790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eda81bf62acb4fa80c06ef0339ff0ff1346afaf0","datavalue":{"value":{"amount":"+0.7757084965705872","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":"Q804291$67FE1620-5034-4610-8539-BA181E547473","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"c39a117a349789e54237c0a3254f5a10c0a6517e","datavalue":{"value":{"entity-type":"item","numeric-id":6830565,"id":"Q6830565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804291$B2680245-4FA6-4CCF-9E33-8866927F1463","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Kolmogorov characterizations of complexity classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Kolmogorov_characterizations_of_complexity_classes"}}}}}