{"entities":{"Q1118403":{"pageid":1129152,"ns":120,"title":"Item:Q1118403","lastrevid":66767967,"modified":"2026-04-12T12:43:21Z","type":"item","id":"Q1118403","labels":{"en":{"language":"en","value":"Communication complexity of multi-processor systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4094804"}},"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":"Q1118403$2959F8AF-0D9D-4122-8184-018871E16F14","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"45369e813b54ac9e9a403f97788e051a1eba5db8","datavalue":{"value":{"text":"Communication complexity of multi-processor systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1118403$E8DA49CB-BA02-425C-8277-750DE238DE69","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c5d20432e1ce477b318eb2a13469981e4ed72b09","datavalue":{"value":"0668.68042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118403$7FF2F43A-F732-4DFB-B8C5-A99BA3670B70","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bc238e8f574c72eddf00ada6c85555f7ba43ef5e","datavalue":{"value":"10.1016/0020-0190(89)90110-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118403$67CF8444-148D-4CFA-8BBC-66F092FCC567","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf6d8016a36fc077e217d8fd7040d00a29999d1c","datavalue":{"value":{"entity-type":"item","numeric-id":671402,"id":"Q671402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$B84A3955-014D-4DBE-B166-392208639C39","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$1D2D2F06-D8E6-4E1A-BB5B-78BDEBCCF586","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":"Q1118403$96F14627-0486-4387-A793-98EAD052719B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f38b941310a9a691e91f68350495cdb23a2b5217","datavalue":{"value":"The communication complexity model of two communicating processors [\\textit{H. Abelson}, J. Assoc. Comput. Mach. 27, 384-392 (1980; Zbl 0438.68009); \\textit{Ch. Papadimitriou} and \\textit{M. Sipser}, Communication complexity. J. Comput. Syst. Sci. 28, 260-269 (1984; Zbl 0584.68064); \\textit{A. C. Yao}, Some complexity questions related to distributive computing, in: Proc. 11th ACM STOC, ACM, 209-213 (1979)], is generalized to a model consisting of k processors connected by a common bus. A lower bound technique used for the original communication complexity is extended for k-processor model and it is shown that the deterministic communication complexity cannot differ more than quadratically from the nondeterministic complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118403$A439C43C-9079-4EFB-B17E-00EFCB5D3675","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"633fdcabf2e644e3cc3929da0924cb1d112f41ed","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$6480C29C-16CA-4463-B1F1-29B31C759C10","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118403$D8A8AFBA-8744-4EC5-BCDC-64DF6EF265D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"99e75c38935b147cca2a0eac1e86993c645e76a5","datavalue":{"value":"94A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118403$FEDCD217-5203-4B87-8D4A-694D4893286E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118403$B066263F-C424-430B-9111-32C47EB29622","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"be1bd819617fb18970bd92ad2c45bed8e50305f7","datavalue":{"value":"4094804","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118403$7EB2D828-05EC-4887-9AFE-90FA93803C58","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"130b8c8ff9581f24d90c088c6d3004037b894759","datavalue":{"value":"multi-processor systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118403$944A2A8B-996E-4B6C-B24B-78AE1DD97F9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0119a0c0ed13d7ec8426c2eea42fb9b463c0bd4d","datavalue":{"value":"Las Vegas computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118403$6C877642-61CA-416D-8F76-3D6E1E6CE9AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c23aa7900c5936b777f3d91dc1f6349283ccbe98","datavalue":{"value":"nondeterministic computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118403$83CA9CFD-27A7-41C1-BA50-DA01C20FDDCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d59f9270ba2c0b3161162dab212fcc774a42eba","datavalue":{"value":"communication complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118403$257FE57B-4A8B-446F-9F2C-B98E244BA9B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49e449974e5abced67bf5ed26284f3738b91515a","datavalue":{"value":"communicating processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118403$7DAFB854-0AE0-4746-80C4-9B2E77AA2B5D","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":"Q1118403$035B7D81-E87D-4741-9826-0F7C98493295","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fc06852e4e0c6a5ed4b08f9af21d3f90ee2da0af","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90110-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1118403$7C0F73A9-54D7-4E5A-A385-54CDC373BBA7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"67539f1ab989d65bce8be28a525d7c99e635370c","datavalue":{"value":"W2043617806","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118403$ED69B50B-434C-4E2F-873D-6819176DC3ED","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7559b2b6b53384708cf9133aa9369cc8b54113b","datavalue":{"value":{"entity-type":"item","numeric-id":1087014,"id":"Q1087014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$A50C67A5-B682-4FC9-9A93-3D98426AD214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f7bd675c24beb1c5ac96ab26a181869bde286bb","datavalue":{"value":{"entity-type":"item","numeric-id":1088398,"id":"Q1088398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$D6C95EF5-CFA2-48BE-A83B-1F2C1A02B0DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57b9be3dea59e8f70331d865383ad1823560ce19","datavalue":{"value":{"entity-type":"item","numeric-id":3340150,"id":"Q3340150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$F9DD417B-514D-4F5D-9A4B-1580B4885FA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"525dd668e08001e4b2c3fca881ad93164bc52ad3","datavalue":{"value":{"entity-type":"item","numeric-id":1069701,"id":"Q1069701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$A4DD8399-12A6-4E2C-BB54-A8B520D5E5AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"761a5977b1a8cb4de06d0c7321118e7752a482cb","datavalue":{"value":{"entity-type":"item","numeric-id":579927,"id":"Q579927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$3ED25922-EC0C-4383-9670-A851BC1E29BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"522e89673cb3122fd0bec879f19808cb3513e83f","datavalue":{"value":{"entity-type":"item","numeric-id":4047029,"id":"Q4047029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$6D69BE4D-3751-4A54-A05F-5447CCC63F0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87f80a083905cd8eff8198cd33ce428915ef1213","datavalue":{"value":{"entity-type":"item","numeric-id":1051066,"id":"Q1051066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$573D792B-AA15-4FAB-9546-C69171165163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9952b5b3566113a7149a7cda5a29bd1aee85c14","datavalue":{"value":{"entity-type":"item","numeric-id":3766832,"id":"Q3766832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118403$A94FEA54-91A6-4A9E-AF69-B8B72AC90057","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0538e0eb82a88e94d08e36851aed8ca43991ff71","datavalue":{"value":{"entity-type":"item","numeric-id":3216143,"id":"Q3216143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22179b51463e8e7ce5ed64504c6062a110cce963","datavalue":{"value":{"amount":"+0.8090174198150635","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":"Q1118403$5413420B-8344-46E2-BC74-3AFA5FBD4CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc0ee0fb6910de1426a43e8611fe7239307c3162","datavalue":{"value":{"entity-type":"item","numeric-id":1097691,"id":"Q1097691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e157c04612ff7ea6bee6d752070e6279cfd37c7","datavalue":{"value":{"amount":"+0.8035088777542114","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":"Q1118403$CFF3F4DA-F296-4CB3-882D-1278924BB12E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"255322b7b9272a7c85dccf3a8bd8d8fb72a96ae1","datavalue":{"value":{"entity-type":"item","numeric-id":4015973,"id":"Q4015973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8734140d27cdb2d83d61c627bd99ffc4ee5944a","datavalue":{"value":{"amount":"+0.7774574756622314","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":"Q1118403$DA474853-7318-4F40-B998-81B1AB131AE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"957e4b8e8b9d38e56030473850fb443f993fbabe","datavalue":{"value":{"entity-type":"item","numeric-id":3766832,"id":"Q3766832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"842f94a2c389ef078e0d46d09e437b9ff3868261","datavalue":{"value":{"amount":"+0.7764337062835693","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":"Q1118403$79E4A307-6D40-47CC-BF5E-26F8FE8F7104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"baadbfc8b9141006898e92d1228ea7e80f622d85","datavalue":{"value":{"entity-type":"item","numeric-id":4875692,"id":"Q4875692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"624eaa6beaeaaa8f5561fffa4a4bbc079baf88bf","datavalue":{"value":{"amount":"+0.7759000658988953","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":"Q1118403$BC06D164-06A0-454D-91E4-4254A2B0AB6B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Communication complexity of multi-processor systems","badges":[]}}}}}