{"entities":{"Q1123616":{"pageid":1134365,"ns":120,"title":"Item:Q1123616","lastrevid":67051278,"modified":"2026-04-12T14:36:24Z","type":"item","id":"Q1123616","labels":{"en":{"language":"en","value":"Descriptive characterizations of computational complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110109"}},"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":"Q1123616$6014879D-8155-43E9-8F53-A5F48F7A7DC6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6a0258eb1a0e146ad681ea3ef051afd060c06b01","datavalue":{"value":{"text":"Descriptive characterizations of computational complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123616$EF8144C9-69F2-4962-88B8-CAAE4DDE0B1D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50fdccc85b155e16283dbf4996f5c2abbee94dd1","datavalue":{"value":"0677.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123616$5CD8051D-EBB1-4B84-AA4E-A80C45BCD10F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a8e94f1a4c443bc7dd17d22ba96bf0cb19437415","datavalue":{"value":"10.1016/0022-0000(89)90019-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123616$DAB431F7-3EF7-403F-A64D-489E86BC3019","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"96a79d9e749e94f65576b1899e96905ca07e98e1","datavalue":{"value":{"entity-type":"item","numeric-id":234593,"id":"Q234593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$5743C5A9-FA8E-4468-A7ED-D6C7FAF494A5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$E725AFD0-AF2B-4E9A-A67A-278F6D9184C5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1123616$45B761D6-EB34-4C87-BA3C-82A81669D016","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"30c41c698ed0cabe164a37cd4b10c56a759284d4","datavalue":{"value":"Several complexity classes, such as Nlog-Space, P-Time, P-Space, and Exp- Time are characterized in terms of formulas of the form (\\(\\forall\\) relations) (\\(\\exists\\) objects) \\(\\phi\\) with \\(\\phi\\) quantifier-free. Different syntactic variants of such formulas characterize different complexity classes. In particular, such descriptive characterizations in terms of higher order logical formulas are considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123616$E9108115-A53C-42C6-B61B-BA41C40C2BDA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123616$E79D9ED9-8E09-4BEE-A365-78787C93AA7A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d3fafd3154eb734f7b76e41eea384714ba648b3f","datavalue":{"value":"4110109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123616$0BD8C03E-4B4B-4016-9E2A-B76D721273D0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"420132b0a86bb9bedd0eeeab0b7b74055a6e96fb","datavalue":{"value":"descriptive complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123616$3EDF0271-32BF-4546-8DB4-A61ED43436EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75ab82a8f4df18227db18bd1221c8cfd9b09d16a","datavalue":{"value":"logical characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123616$71E03B5D-4A40-4EC3-A7F7-3939A256356F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28ad9560d49e887ef3a6d81711e94252a33be344","datavalue":{"value":"of complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123616$00A3E94E-F96E-458B-B4E2-C210BB1F17C9","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":"Q1123616$0ECEB629-6BA6-4577-B85A-49BCD947C283","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cd996c979ad9bdf1b0c5c239811448fd66434d94","datavalue":{"value":"https://doi.org/10.1016/0022-0000(89)90019-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123616$0D459BD6-9AA4-4B91-A3C6-109889E5A067","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d32636aa907d27447a5ff5e48e54b2e9eb305a69","datavalue":{"value":"W2079745007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123616$AC8F8E06-E91E-443F-A0D1-6BEF1CE97E8D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3d4f90fa52e835209baaf1ee94cf3ff7e79c103","datavalue":{"value":{"entity-type":"item","numeric-id":5619067,"id":"Q5619067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$8A6C7A2A-EFCB-4B68-B2BA-655EAAEC5AA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8973abb951181b5865d7e8e53e525f0e4b9b6f41","datavalue":{"value":{"entity-type":"item","numeric-id":4075450,"id":"Q4075450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$C194E77F-5F91-4229-9B3F-D7FA4C7C20F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f133b74af7d5821d23702be11600a40ece90371a","datavalue":{"value":{"entity-type":"item","numeric-id":5645404,"id":"Q5645404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$42D0F704-087E-48A1-B08E-F2889593BB36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79e95288fb3703a153af69a0fa87ef12ad85fe48","datavalue":{"value":{"entity-type":"item","numeric-id":1088983,"id":"Q1088983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$D75BF564-37A9-499F-BE8F-C29EA7EA7C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b83d2aee3aecf6a04f21544f51ee6adfcf5f9fef","datavalue":{"value":{"entity-type":"item","numeric-id":4177549,"id":"Q4177549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$EF48FE2B-937C-4453-9688-C333027C56F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39ff29fc9ad9e25bd29bf653f6c7cf5c641d388c","datavalue":{"value":{"entity-type":"item","numeric-id":3220555,"id":"Q3220555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$0A26721A-E5FA-474B-95E7-82648D95C230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f55d8e9e513e18f865fb488ac9b15306f0f42c0f","datavalue":{"value":{"entity-type":"item","numeric-id":1151060,"id":"Q1151060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$DA3253A0-B686-4997-BC3B-C7B03CEF0B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7560ee1eeb9a13415ac8537672089a0c086ad04","datavalue":{"value":{"entity-type":"item","numeric-id":3235339,"id":"Q3235339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$4E2E69BA-A976-42B1-A02D-F0366BFDE9D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$3A7B2E13-3F9B-406B-983F-5E42FF455060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0839e7e46510112865b452a6ed8d8dd889a4c60","datavalue":{"value":{"entity-type":"item","numeric-id":4058132,"id":"Q4058132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$BA6C57D0-090E-4B82-9CF2-5D33B9082DDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9f9e080f623f4cb3a030a9346791873bf61f74d","datavalue":{"value":{"entity-type":"item","numeric-id":3880831,"id":"Q3880831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$9602717D-2926-45BF-9A99-119E9EE86818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"993bffc544b04077fe2e3fc10963180ccc7177ec","datavalue":{"value":{"entity-type":"item","numeric-id":5625130,"id":"Q5625130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$FD8BE9BD-BD34-4595-ACC8-E240FCD46E3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf79dd85aa883318752687b0ce6dfc9ed9e62cbd","datavalue":{"value":{"entity-type":"item","numeric-id":2550291,"id":"Q2550291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$865DE4DF-D1DF-40EA-9D09-4E1DCBC8B442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be154b266f49b889b70e2e16e1ef5f70c091bcdc","datavalue":{"value":{"entity-type":"item","numeric-id":5732647,"id":"Q5732647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$70508D42-3832-45B1-8AE8-276F4450B5B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01be0fba01f41010482a9b92a86a128f4b1b9e6a","datavalue":{"value":{"entity-type":"item","numeric-id":4122837,"id":"Q4122837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$F37BD2A1-55AD-4136-8769-7A0931BDB4EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"451e4670e349b30bf00735806c505c29fb4dea2b","datavalue":{"value":{"entity-type":"item","numeric-id":3719820,"id":"Q3719820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$76E343EA-1B39-4A10-8242-8935426155C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b67ee9815f7ab3c8b2b4907677d99ca915d101b0","datavalue":{"value":{"entity-type":"item","numeric-id":1164622,"id":"Q1164622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$E0215217-4785-42D0-90CD-CD316229FBA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a675fab4321817783597d6a1b8160efcb24c4ec","datavalue":{"value":{"entity-type":"item","numeric-id":3753525,"id":"Q3753525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$57D6B1AA-5799-4025-AAB5-7FEF4679CAB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ca7a1acbb96c14c8f84c4ce6e6462daf757716","datavalue":{"value":{"entity-type":"item","numeric-id":3773337,"id":"Q3773337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$CDC53B93-58C6-4413-B995-99747032495A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7402dc5bdf53dcf826b894508745d7a339429a41","datavalue":{"value":{"entity-type":"item","numeric-id":4775859,"id":"Q4775859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$CAA9D508-7332-4B1E-A55E-1BECD91AC0CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e28d9ef86be0015aac95587d4e909c688b52de6","datavalue":{"value":{"entity-type":"item","numeric-id":5536268,"id":"Q5536268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$7F26FD25-DDAD-4ACA-A1A7-38B837E16340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$E878A2D2-AB25-42F1-9B05-6E120FF1B678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3961712aa73d0d7e49904f6e1571dab96fdf8ac4","datavalue":{"value":{"entity-type":"item","numeric-id":3325707,"id":"Q3325707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$834C21A9-1648-4C44-A245-C6A9BC527FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e352c0c79a06f6de0a8b9916dc2f414ddad83f78","datavalue":{"value":{"entity-type":"item","numeric-id":3797174,"id":"Q3797174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$13096A89-E4C3-49DD-A4BC-E4BC5BFFE4D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$1657C8A4-5CED-4E1D-8A80-12BE4DC2E554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6667d29690da802e41dbaa0f1f4db3280cf4b19d","datavalue":{"value":{"entity-type":"item","numeric-id":5815606,"id":"Q5815606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$DFE151C8-DE6D-4E13-AB6D-FFF383D408BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dca7bf9ff748343f2efbe736997f3fd4b0e9f589","datavalue":{"value":{"entity-type":"item","numeric-id":5623654,"id":"Q5623654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123616$994FF873-41F6-4C3A-8FA9-E284D4D7289A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b14ca55b8874e69e9315e4ec246e59bcb66b0f5b","datavalue":{"value":{"entity-type":"item","numeric-id":3974868,"id":"Q3974868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6136939fc86816ceeac0cbb6c1113757923da859","datavalue":{"value":{"amount":"+0.8171651363372803","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":"Q1123616$4B49A9F5-C796-4DFE-8473-878189A17E52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c370c38dc3cc02d897b1ba8a0dc6bc5072f0dbd","datavalue":{"value":{"entity-type":"item","numeric-id":4644504,"id":"Q4644504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6136939fc86816ceeac0cbb6c1113757923da859","datavalue":{"value":{"amount":"+0.8171651363372803","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":"Q1123616$7076BD1A-2356-4680-8857-65E5E3F230CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bcd5027a71ded3df63407d455b4c25b2572bc1a","datavalue":{"value":{"entity-type":"item","numeric-id":4227581,"id":"Q4227581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e763b748a9b58f595999be8f0906ccdff97bed75","datavalue":{"value":{"amount":"+0.8163586258888245","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":"Q1123616$81CE616C-0D10-446E-815C-DCB71CD5F844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ac0b45b81196e55c0ca01b241e42e20b3cc9590","datavalue":{"value":{"entity-type":"item","numeric-id":5179012,"id":"Q5179012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e763b748a9b58f595999be8f0906ccdff97bed75","datavalue":{"value":{"amount":"+0.8163586258888245","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":"Q1123616$94293A1C-283F-429F-9669-BA7F9C58E83D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd529569030221fe02b566353d8784b62fa3687c","datavalue":{"value":{"entity-type":"item","numeric-id":4425337,"id":"Q4425337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d637da698ed02d6c0bfddfdcdc49ffc9d8543d3","datavalue":{"value":{"amount":"+0.8115780353546143","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":"Q1123616$E89AF0C9-C693-4560-B04D-12629F82C4F4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Descriptive characterizations of computational complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Descriptive_characterizations_of_computational_complexity"}}}}}