{"entities":{"Q1115619":{"pageid":1126368,"ns":120,"title":"Item:Q1115619","lastrevid":66765000,"modified":"2026-04-12T12:42:11Z","type":"item","id":"Q1115619","labels":{"en":{"language":"en","value":"Searching with known error probability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4087035"}},"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":"Q1115619$EA5F1A82-0C45-4923-AC1F-AA0334D45624","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"216e744b0280164c7f4eb199ccbe4fecb555da52","datavalue":{"value":{"text":"Searching with known error probability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1115619$0ABD8134-71D3-4A7C-A15D-390190555861","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6306d5bab6433ee647f31e11f38e3e2ede280010","datavalue":{"value":"0664.68062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115619$131977A3-0893-42B2-AAA8-1E4D5777AF96","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6283c2aabfdb83284512e00c2f1136615c4ba027","datavalue":{"value":"10.1016/0304-3975(89)90077-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115619$E19B0D8C-419A-4D63-83B4-DB16F840EC4D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"685bde8c367f18365d551a594d09a5ad87b8d248","datavalue":{"value":{"entity-type":"item","numeric-id":235631,"id":"Q235631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115619$F47BA6A8-1393-45EF-BC89-7D48BBD0531E","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":"Q1115619$0870931D-8296-46A8-A9D4-716F1F3CCE95","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":"Q1115619$2EEA3FB8-2E38-4BF4-B438-A563B73C42A4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0547985516c68779b4e18e24dd25487c36b7bbb7","datavalue":{"value":"We study the problem of interactive searching in a set of numbers using comparison queries, under the assumption that each answer can be erroneous with a constant probability p and that a given reliability \\(0<q<1\\) of the result is required. The search is considered in three versions: continuous (the search space is the interval [0,1] and the unknown real x has to be found with a given accuracy 1/n), discrete bounded (x\\(\\in \\{1,...,n\\})\\) and discrete unbounded (the unknown number n can be any positive integer). We prove that in all cases the search is feasible for any n and q iff \\(p\\neq\\). For \\(p\\neq\\) an O(log n) searching algorithm is given in the continuous case and \\(O(\\log^ 2 n)\\) algorithms in the discrete bounded and unbounded cases. For \\(p<1/3\\) or \\(p>2/3\\), O(log n) algorithms are given in each version of search.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115619$12BC2623-7F7C-4D32-A922-DEA5E5A00E26","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115619$45B2DEF8-563E-4347-A7F3-A5B660649BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115619$DF1AA4B3-4DD6-4B3E-80FF-37EF5D0EE8A1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ec5a196a00d0d1fbce25f89c4bd4295d94f0dba4","datavalue":{"value":"4087035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115619$E465B172-29BC-4654-930F-C0E3BBF92E74","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e36e5a47a0cffb96060823c8dbdcbd989b7145f","datavalue":{"value":"continuous search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115619$AAA46496-1572-445B-84C7-D3468220D260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88e31f13805c800dfafa97874680e3fc933a6be5","datavalue":{"value":"discret search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115619$B77AF990-5C52-4D88-92A3-9A224611D256","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dea71bce5cffc7582f5a9dcabfa20d750657152","datavalue":{"value":"interactive searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115619$FF27E39C-D6DE-4FC9-A6F4-847994135B2E","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9dfd78a7dbc001d7d5313c6b887c133937d21c10","datavalue":{"value":"Q56039268","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115619$247027ED-69B9-4571-BD81-3BC43CBFC8E8","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":"Q1115619$308F89B5-D3D5-4838-AD7A-3CC7289D540A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dc0dcfd0c4d884b3da2492ab9e298f40db02c29f","datavalue":{"value":"https://doi.org/10.1016/0304-3975(89)90077-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1115619$A46C884F-F4EC-4006-87B0-7750CDEACE50","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ce4f3892f467ba37a384056819d91bd6031b3b15","datavalue":{"value":"W2131306093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115619$32EC7472-9ACE-4616-BBDB-65185D7F4049","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddd7cf5c3cf20a3faedc8fb513c29ca711e97cb6","datavalue":{"value":{"entity-type":"item","numeric-id":1229581,"id":"Q1229581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115619$8DA90DBC-9722-44F1-8A66-58FE92379C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb953e83005013fc04f127863b0565d2a756d106","datavalue":{"value":{"entity-type":"item","numeric-id":1090471,"id":"Q1090471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115619$9E868C3C-4843-4912-BDEE-0197320E69B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dacc3c87789ddc6c17665b4d61a7d982c03da94d","datavalue":{"value":{"entity-type":"item","numeric-id":797505,"id":"Q797505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115619$0A22534E-24E3-4641-BFA3-B5DFC62DA46F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d25de6edbffbbaea8e3baa0c3d34a005f6b4e3e6","datavalue":{"value":{"entity-type":"item","numeric-id":5512642,"id":"Q5512642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115619$C8E344F8-C4B3-47F0-9D00-314C1773FCD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca4d55e2805f215a7a35e3c231c9cfbc5b6ec954","datavalue":{"value":{"entity-type":"item","numeric-id":1144379,"id":"Q1144379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115619$D913F046-F975-40D4-B799-1BB89D65104A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b9aa09b78a4b56c9b54a7b783716c87328e3887","datavalue":{"value":{"entity-type":"item","numeric-id":5627976,"id":"Q5627976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115619$C8C367D2-A5A4-4CAB-8F6E-D22409F02157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfa4c64477270a34e60163db3f94c231bcea10f9","datavalue":{"value":{"entity-type":"item","numeric-id":3325513,"id":"Q3325513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115619$2566D244-8298-4623-B305-B4963F048FD4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fa54723af140df8d3f975f4c525590144c756e2","datavalue":{"value":{"entity-type":"item","numeric-id":5402561,"id":"Q5402561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8d4f89733f74dec7d9f744df2ad19abfe0b8510","datavalue":{"value":{"amount":"+0.884231448173523","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":"Q1115619$CD28A3DC-7F09-41D9-A83D-90A52ECB86F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20a8c1cc6c861599275202797551ea6f530fffc7","datavalue":{"value":{"entity-type":"item","numeric-id":293463,"id":"Q293463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"713cebe6d69f8afdd654340502dc031326aa868c","datavalue":{"value":{"amount":"+0.845512866973877","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":"Q1115619$7538C567-0131-45FF-858E-57795D73F4CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13307cfdef7b019fad51f0bd62422f1e132983b1","datavalue":{"value":{"entity-type":"item","numeric-id":1329070,"id":"Q1329070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ee06fdc2b4d0edf7e3792ea53cca3ac0fedf47a","datavalue":{"value":{"amount":"+0.8307018280029297","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":"Q1115619$A1E811BE-DA5C-4432-AC45-102DDD54DADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff37aa27abef0d18332eaf90f2ac8144cc2f13f9","datavalue":{"value":{"entity-type":"item","numeric-id":5958337,"id":"Q5958337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f98847449b9ec4bafdbcb48cc1f3e4c14a4cc8d","datavalue":{"value":{"amount":"+0.8211069703102112","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":"Q1115619$4653AE5A-F72B-436A-918D-F7BD47CDA2A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eef5803fc958640c9c164a2dc07d82965a3aa72e","datavalue":{"value":{"entity-type":"item","numeric-id":5191681,"id":"Q5191681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f98847449b9ec4bafdbcb48cc1f3e4c14a4cc8d","datavalue":{"value":{"amount":"+0.8211069703102112","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":"Q1115619$A2D6D07B-2FAD-4550-858F-01B0E80EB063","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Searching with known error probability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Searching_with_known_error_probability"}}}}}