{"entities":{"Q1194380":{"pageid":1205129,"ns":120,"title":"Item:Q1194380","lastrevid":66830928,"modified":"2026-04-12T13:08:52Z","type":"item","id":"Q1194380","labels":{"en":{"language":"en","value":"Complexity of verification and computation for IBC problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 64311"}},"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":"Q1194380$65FEEEAB-0AFB-49CB-8DF8-2DD0519F0390","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"279fbf235d29bda808c7605477bd8e2023adb721","datavalue":{"value":{"text":"Complexity of verification and computation for IBC problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1194380$45B92FE7-CAA9-4D79-AEA7-D70188732D29","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ca88349d71cc8dc8fcf3cff6373adbb5057708c2","datavalue":{"value":"0755.65149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194380$4A92CCD4-8E43-47D4-B2D2-CC5924C94BB4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"35f76829675f2d56477fe38be9782c99371ea688","datavalue":{"value":"10.1016/0885-064X(92)90011-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194380$195962B0-28AB-4624-9EA0-063432486F15","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194380$1757DCF5-5F65-4560-8125-E00FDD95F79D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5fd62271fe98c7ff9916cafed51cf35315eeeb31","datavalue":{"value":{"time":"+1992-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1194380$60DCF345-CCF2-4308-B0CD-D43D2B036BE4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c44ff9b32231be52bd18c3a749d3ca02677aa673","datavalue":{"value":"The author analyzes the complexity of verifying whether a given element is within \\(\\varepsilon\\) of the solution element, which may be contrasted with the complexity of computing an element that is within \\(\\varepsilon\\) of the solution element. In information-based-complexity (IBC), where the minimal cost of computing an \\(\\varepsilon\\)-approximation to the solution element in different settings is studied, verification can be easier or harder than computation.   The author studies the probabilistic complexity of verification as a function of the error tolerance \\(\\varepsilon\\) and the probability failure \\(\\delta\\). It is assumed that the solution element is specified by a linear continuous functional defined on a Banach space equipped with a Gaussian measure.   It is shown that for fixed \\(\\delta\\) and small \\(\\varepsilon\\), the complexity of verification is zero, whereas for fixed \\(\\varepsilon\\) and small \\(\\delta\\) the complexity of verification is essentially a function of only \\(\\delta\\) and may be exponentially harder than the complexity of computation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$AEDF5B81-6250-4C7B-8592-67442F908663","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194380$EC7E75E0-7B24-4BDD-A02D-97D939613A5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ae13d34166b4c2d458855f3bc2c684b2cb32f7b","datavalue":{"value":"65J05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194380$B47C1583-AB54-4AE4-83B4-60388683BD17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194380$53646F38-4A6F-4CEC-8765-05AC17B8F6E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bd07443054e4950f02b42390c3eb73512ab8ff3a","datavalue":{"value":"64311","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194380$58A51BBB-87C5-4C85-8BB6-2A0416D4C86A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7dde8a3acbf5a51e4a3d382793141716073998d1","datavalue":{"value":"verifying","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$B2FBE1ED-2BF3-41AF-BE00-2A91488FAA2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1c8b748fdc019215a99133528e70491a123618d","datavalue":{"value":"computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$706F74DE-80F0-4B8B-A871-88D29690975A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c15fa59b8f1ce206f81cf0de2875c3450ab5f6af","datavalue":{"value":"worst case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$295D2D84-DCDF-4494-9F70-6662C19156F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07bcbf7ffe4deb0cc70e111de20fcf133add070f","datavalue":{"value":"probabilistic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$588065DA-A124-413A-90D1-18F5C2341686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"adf8768e8316bddd41d7326755ff53a6ce8044ec","datavalue":{"value":"error tolerance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$A3F3CD79-F96F-4E8A-B841-24512610562B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16be26a316ca44949f7b996d0a09e3e3de80a019","datavalue":{"value":"linear continuous functional","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$56622BDA-782E-4246-AC18-27ECE886279F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79868fa7d2ed2a6553b37c589c14ecdcfeb2d4ec","datavalue":{"value":"Banach space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$D22C43B2-EC7E-4AA7-97CC-90775BE04C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbc0d839b0f7f7e7f87a5955f544be347954c5ee","datavalue":{"value":"Gaussian measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$9B77AAEC-6A75-4C28-986B-DC9D2C64B459","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b343d76b5a54ac856d8d02309b9ae7b3cb9b6a3","datavalue":{"value":"complexity of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$F36A67F6-A924-4A52-8809-000F38C1D153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e5c050772bdddd7dd8c52388ff1fe9e49b2197b","datavalue":{"value":"information-based complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1194380$434F934D-C918-40A8-BEA4-73BE25FBD837","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"022cc2ef7a956d48f142cada4328c1d9ba0d76f3","datavalue":{"value":{"entity-type":"item","numeric-id":346289,"id":"Q346289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194380$39049CB1-3D9E-4443-9603-215D521417A2","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":"Q1194380$11F21749-AE78-4790-95CE-FA7B0931C376","rank":"normal"}],"P223":[{"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":"Q1194380$D3081C1B-C558-4DC8-8E7D-A2312E7B50F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cd7294209ed8f0ac33248d2590cda366a477fcd","datavalue":{"value":{"entity-type":"item","numeric-id":1100662,"id":"Q1100662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194380$1DE2C6E3-7141-4C00-B8D9-87C8E093568D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9143ecd4de54a1611b4e5afe91d458e2a75679df","datavalue":{"value":{"entity-type":"item","numeric-id":1217911,"id":"Q1217911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194380$1169BC53-41D2-4ED8-900D-D1CD31D6B644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67d9655972cb54da769f70190b945e3f3ca313e0","datavalue":{"value":{"entity-type":"item","numeric-id":1194381,"id":"Q1194381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194380$DB9A2BE7-29A7-4D11-9F86-70E4B6E7DA58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faf1e98f17e1410c28a20c74dcf390e7440c1a01","datavalue":{"value":{"entity-type":"item","numeric-id":3993279,"id":"Q3993279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194380$81FF2247-C285-48B6-8E5F-28E972D7F8B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0016a8b912e2f4de7ef7d34b1fcc11cb6a5b4502","datavalue":{"value":{"entity-type":"item","numeric-id":3883494,"id":"Q3883494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194380$447A0C2F-90D6-44DA-8AA9-48D700F331E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"979f19b8532c70bfe7eec3c3add38c134ffedda3","datavalue":{"value":{"entity-type":"item","numeric-id":3938928,"id":"Q3938928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194380$2D50E91D-E159-4466-B0E6-3AE4EBB5834A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4ee61ff8e6a3ef017b28d8d1c49902c2ac0a5fc","datavalue":{"value":{"entity-type":"item","numeric-id":3355138,"id":"Q3355138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1194380$573451D7-020E-483A-9465-A18A087CEE58","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d6c8ee3d108801f27819aa038cafad815a1fb9db","datavalue":{"value":"https://doi.org/10.1016/0885-064x(92)90011-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1194380$95EF05EB-1C0E-410E-8F3F-D814B6485CE7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d22bc2d4879dabc50b03061fa83982f5b695190b","datavalue":{"value":"W2133277606","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1194380$70428730-40F3-45BF-9E93-F144A3ABFAF7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c315be778a6d3f33af9e1711cf3933d3f19bae65","datavalue":{"value":{"entity-type":"item","numeric-id":1194381,"id":"Q1194381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d231ff50170cf4810c557c993ab1f4c795561bf","datavalue":{"value":{"amount":"+0.7923555374145508","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":"Q1194380$8B441DA6-305B-4683-A9A5-0DD24EEE58FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79a4506bb6ffe460b408f896d837a51301a05efb","datavalue":{"value":{"entity-type":"item","numeric-id":3992024,"id":"Q3992024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f79994260bb656eacbca5b52e3c7ad8b96675d0","datavalue":{"value":{"amount":"+0.7893153429031372","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":"Q1194380$EAC399DA-436D-40EB-A079-7AD5938A7FFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5952ac775bbfb147a117d40dfb2f87867ab6931","datavalue":{"value":{"entity-type":"item","numeric-id":1092660,"id":"Q1092660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11d5060e5e9c47d35d55418034b7af73df15113e","datavalue":{"value":{"amount":"+0.7295796275138855","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":"Q1194380$C5947C87-D19F-4A9F-9D61-A402220ED9A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8896a166e8ad5722141d83115f2d9307db687b6f","datavalue":{"value":{"entity-type":"item","numeric-id":1342516,"id":"Q1342516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d51a1569cc5ccde35dac7996a005606e79662832","datavalue":{"value":{"amount":"+0.7205321192741394","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":"Q1194380$13CEAA37-DAC9-43D3-8BDE-5EF43B73BE18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d206644b28fa4daf0c16b8f7ede26605f6363684","datavalue":{"value":{"entity-type":"item","numeric-id":3780359,"id":"Q3780359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a0c66c518b9040c733a5596e045d1f3e6d4b507","datavalue":{"value":{"amount":"+0.7150483131408691","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":"Q1194380$06B722A6-3975-4E95-95F1-7ACC896BF004","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of verification and computation for IBC problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_verification_and_computation_for_IBC_problems"}}}}}