{"entities":{"Q1190986":{"pageid":1201735,"ns":120,"title":"Item:Q1190986","lastrevid":69856965,"modified":"2026-04-13T10:48:42Z","type":"item","id":"Q1190986","labels":{"en":{"language":"en","value":"Multi-oracle interactive protocols with constant space verifiers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 58808"}},"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":"Q1190986$EAE2B86E-0D3E-4DA4-A094-006B4472AE34","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"49547202a7b2d2a2f58e9ec6d410740f5c43dfd0","datavalue":{"value":{"text":"Multi-oracle interactive protocols with constant space verifiers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1190986$ED281B1F-3337-41AA-836C-A202E8C17057","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"65ed66f52c322e55e06e4a1bb1771f7c47458d64","datavalue":{"value":"0757.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190986$276546DD-27D7-4F40-8621-53F1384D6CB5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"67978881fe7c97e0b5179fd38e3e4778e548acd6","datavalue":{"value":"10.1016/0022-0000(92)90021-A","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190986$EDB5A827-CF3A-4B79-80F2-46C75E4104DF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"811a6b2b66f4789d1563056800fcb38db50142e1","datavalue":{"value":{"entity-type":"item","numeric-id":321301,"id":"Q321301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190986$F5C5E961-BE8F-40C5-8117-5F8C9B97BDEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4fbe35cb61496fa8363dcdb2d9d3a4d54bbef6e2","datavalue":{"value":{"entity-type":"item","numeric-id":6480586,"id":"Q6480586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190986$39D751AA-AD99-4822-B2C4-1917CEB94BE6","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":"Q1190986$1EA58FE0-C066-4390-A621-6364F149D4F7","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":"Q1190986$DA7C37CC-DFF7-4373-B055-A86EBDC02C31","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"160d338e869bcd45da4658f30a17175ad3e871f4","datavalue":{"value":"It is known that the process of generalization of the original (one- prover) interactive proof system notion into the multi-prover one followed two different paths, thus resulting into two models -- the one where all provers cooperate with each other, and the one where provers oppose each other with at least one trying to help the verifier (and the other trying to mislead him).    The paper deals with the power of constant space probabilistic verifiers in both these multi-prover models. Using an ingenious digital signature, a protocol by which a finite state verifier simulates a Turing machine in both opposing provers model as well as collaborating provers model is presented. The result for the opposing provers model is then used to prove undecidability of the question whether a player in a reasonable game of imperfect information has a probabilistic strategy which wins with probability greater than \\(0.5\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190986$CC78D1F8-95B9-44ED-A269-238860578F39","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190986$48586821-B915-4358-934C-1DB814EFF8D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca8c16691e9ec83d46a3995338b09d48ac9660ac","datavalue":{"value":"68M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190986$D671DE72-CB3C-4071-B353-17388C450877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190986$231A22E2-E55C-4BBF-A241-063BC855D158","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"58e311731e595dd65d78e757583f2e3de0c90e6d","datavalue":{"value":"58808","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190986$16155B56-7DEF-47E8-91F4-588286258C0E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64d2330f317bc48b9444caf705aced9d63bab5cd","datavalue":{"value":"interactive protocol","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190986$EB8E4155-D5B4-4180-AE9B-621E87750718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b923aaf950dbb57dcb08eb03c5899b5ac37a584d","datavalue":{"value":"reasonable games of incomplete information","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190986$08A176E7-1766-4B26-AC4C-29671A2E7D8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cf9939c540359b39cf519b4f8d65fe930cb7444","datavalue":{"value":"opposing provers model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190986$67F8F98E-1806-49F3-B187-79290585AA55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75613a70ed908210cf279e76c9e01902c463474a","datavalue":{"value":"collaborating provers model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1190986$CEF67DC5-2FCA-4EE6-8DA9-ACF0059C9C02","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190986$6CCF9605-C14A-4A09-A9E4-A605DD9A54C4","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":"Q1190986$3647C8DD-17D3-4361-AB5B-EA2B9C54C6D5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8d154393ad0afc2810aee62966ec1a7a0324acf","datavalue":{"value":{"entity-type":"item","numeric-id":1210334,"id":"Q1210334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190986$FBC7B0A5-14B4-4F89-9BC6-DD198B0F3A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22088cdb6db773f078144ada8ccb5e1eafe67b32","datavalue":{"value":{"entity-type":"item","numeric-id":1824400,"id":"Q1824400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190986$E36481D3-B5A6-4555-B495-14CDF24D0F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9927d2b4fc28de88e86da105510c7559458eef96","datavalue":{"value":{"entity-type":"item","numeric-id":3204032,"id":"Q3204032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190986$48E33BCF-66E0-45BB-ADB1-C27FC7180611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae477ba2300400eec2908d55329cb4248dc074d4","datavalue":{"value":{"entity-type":"item","numeric-id":3833627,"id":"Q3833627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190986$70CF1A79-549E-4710-BEB9-B828C0F48514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190986$2532B5FE-5BD4-44F7-8705-A63924F9324D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a311e7ea5e9c4b3c79d5eb4c907cd6989b685383","datavalue":{"value":{"entity-type":"item","numeric-id":800838,"id":"Q800838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1190986$846A34B8-3D84-495B-90F9-59A40A26CC04","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"09c06517dc4853cbe4e015e03227bc1765cbaa53","datavalue":{"value":"https://doi.org/10.1016/0022-0000(92)90021-a","type":"string"},"datatype":"url"},"type":"statement","id":"Q1190986$3B3143B5-E025-4C6F-B565-11CE7F92F3E6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"51d67e0c19dfff086ada48cca2cbb6fb39193024","datavalue":{"value":"W2007426955","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1190986$3D690B42-4756-4825-8509-6278938E75E0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0c87d7511b811ce88027d34ab476b12ff014f5b","datavalue":{"value":{"entity-type":"item","numeric-id":1341733,"id":"Q1341733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"521b1f1ff50277dcf56ac689670a5f7095df124c","datavalue":{"value":{"amount":"+0.8139840364456177","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":"Q1190986$8BFD6743-9B19-405B-ACF1-A977D106E1DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1abae5371c22a33e595912f09f626f5887a0bae","datavalue":{"value":{"entity-type":"item","numeric-id":3975930,"id":"Q3975930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f67862789696ca973d016c8ef4f29edd772ad94","datavalue":{"value":{"amount":"+0.8002232313156128","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":"Q1190986$2C58B6A1-3E2B-4AAB-B725-B6A86B8DE3AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12e35dc2f78a6fdd66819e9c777c1c4d3d9c6b96","datavalue":{"value":{"entity-type":"item","numeric-id":5946704,"id":"Q5946704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12f234a691476c154a55bbda7e749dfdc0412d06","datavalue":{"value":{"amount":"+0.795883297920227","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":"Q1190986$9276051C-2909-4E6E-9C2F-84F44CEB268F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Multi-oracle interactive protocols with constant space verifiers","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Multi-oracle_interactive_protocols_with_constant_space_verifiers"}}}}}