{"entities":{"Q1106664":{"pageid":1117413,"ns":120,"title":"Item:Q1106664","lastrevid":69656541,"modified":"2026-04-13T08:30:17Z","type":"item","id":"Q1106664","labels":{"en":{"language":"en","value":"The complexity of parallel search"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4062583"}},"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":"Q1106664$8B23C95E-35AA-4379-BDE4-842816D3E1E6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"de258278af263b6a1ebe956f08f11fcbcf73750d","datavalue":{"value":{"text":"The complexity of parallel search","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106664$67EA7F49-57C3-45B3-B0FA-C2834747778C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"273d7697493106f41a692c4915d8fb96fa85ee28","datavalue":{"value":"0651.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106664$85CC36A1-CBCB-4F91-BD9B-B3AFFC280C90","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2a5b8a99dc8b66b07463527372ca6e257ff7c1cb","datavalue":{"value":"10.1016/0022-0000(88)90027-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106664$B72A10C6-26F9-4F5A-8FD3-5478F2DF564C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7f03cf6abbdf2fe79063aacbf005af333537b97","datavalue":{"value":{"entity-type":"item","numeric-id":619905,"id":"Q619905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$4DF3CB46-7E4D-49F3-8FCE-6601DD8C2972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb601144f50446ab918878975754b8b11688e0e2","datavalue":{"value":{"entity-type":"item","numeric-id":477097,"id":"Q477097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$7E50AEB4-6DFF-482E-89F4-D09A6FB011B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a028a6348dcfc7b43c17e257a75b67ed9a2b7db","datavalue":{"value":{"entity-type":"item","numeric-id":178716,"id":"Q178716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$033A9477-CE4B-4A99-A409-7980A7FD4241","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":"Q1106664$6E14A4CF-1751-484F-A98B-0266F989EFBD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1106664$BD61E238-F00F-48EC-AC94-0775BC8029CE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"23b6c072d0bf8678c874cd9d93028b2dc4839ae4","datavalue":{"value":"The subject of the paper is the computational complexity of some parallel search algorithms within the framework of independence systems.    Evolved from earlier work on parallel algorithms for concrete problems (the determination of a maximal independent set of vertices or a maximum matching in a graph), the research results in a parallel analog of the self-reducibility process, specific for sequential computation.    Three types of independence systems are considered: matroids, graphic matroids and partition matroids. Lower and upper bounds on the deterministic and randomized complexity of these problems are derived. These bounds may be used to highlight the processor-time trade-offs that are possible. In the same time, it results that randomized parallel algorithms are much more powerful than deterministic ones, and even the randomized algorithms cannot make effective use of extremely large numbers of processors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106664$B9C31B63-7AEA-4930-8955-8E6471B8AEB8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106664$06DEAD28-63E0-4D82-BEE3-3387EF73E182","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106664$4E7AB523-9703-4033-A94D-8416002A206A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106664$07FD7F0C-10AA-406F-9341-B45B940EBAE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106664$846DFD17-7B03-4136-A54F-3A6FF1EEAC24","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e44b5c8a783b98d1f9bb55d3b068329304e259d","datavalue":{"value":"4062583","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106664$FFA76A42-FB0F-48C5-9B74-A5F40D5670C3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da2bb54afee469b253011c2b7b73ccc313a34cdc","datavalue":{"value":"deterministic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106664$07A8AAD0-65EE-467F-B18F-0164D743D738","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106664$3BF42DC4-99A9-4AFA-9FBC-F4210BE23CA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae825cca93bbd40be3a29f025f781f23f8b04bd2","datavalue":{"value":"parallel search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106664$69851A63-F325-4A6D-B105-AC717E778E9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5df066372b43ee0a234844149e91ea9cdd335344","datavalue":{"value":"independence systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106664$3E3CC62F-B735-4D7B-9BDF-293C10BDCF96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39ec4307b26d786312cb390856b9060d3bf22c8","datavalue":{"value":"matroids","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106664$EFF35A8F-5394-43DF-BB13-B60C076AC493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccb70a21798131aade846f0b570573d473295475","datavalue":{"value":"randomized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106664$1574325A-CB36-48B7-B149-05141746FDC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5912247647404e3a7099a9806b36ce2df7e95d8d","datavalue":{"value":"processor-time trade-offs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106664$7158C9A8-1C36-4093-852E-816F39E71172","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7fe7620e945054cf6aa8da466a7cb93509e71b4a","datavalue":{"value":{"entity-type":"item","numeric-id":1612676,"id":"Q1612676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$4EFCAF1F-8307-4AE2-8E42-2B4CFAF239CB","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":"Q1106664$65DF387F-F641-4CCB-AF14-6CD0CE40768A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83c6293f25e8bc7e1747aa6978fc2fd52b5104b6","datavalue":{"value":{"entity-type":"item","numeric-id":1141153,"id":"Q1141153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$6ABDFB57-B3C5-4F13-A70E-697A724D0AA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c6c338f74f8724c3697d5b86b62f3375f4fb35b","datavalue":{"value":{"entity-type":"item","numeric-id":1253482,"id":"Q1253482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$DB5F735D-F0A8-4CB5-A4B7-68E9652FFC10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"850f4bd9fca000f728f3a248d4293b4cf8aeb4d7","datavalue":{"value":{"entity-type":"item","numeric-id":3204465,"id":"Q3204465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$F967A746-FC2E-4023-869D-AB2DF2714922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"240763e838157d05230d2e59c5ec40129fb34526","datavalue":{"value":{"entity-type":"item","numeric-id":3896841,"id":"Q3896841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$485B1758-8E81-46F8-AC32-5673E1F88D8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08dd2cde602af137c52ba4f69c22bcd86e50c081","datavalue":{"value":{"entity-type":"item","numeric-id":5332577,"id":"Q5332577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$801D27A9-06D8-4F69-9799-3EA78FACE665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9b712e361bbfbc97c265dcc3e2463de06c2cf58","datavalue":{"value":{"entity-type":"item","numeric-id":1103639,"id":"Q1103639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$E1A40EE6-5BC0-489D-B8E2-752A9FA7409F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$C30CF0FF-0DC4-4854-81E8-F612DD760C3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a5dd87f9b47ea169d77fccc0d3b1ab0e65eb8a1","datavalue":{"value":{"entity-type":"item","numeric-id":3756533,"id":"Q3756533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$F810D8AB-D58D-41E7-9E77-2E2798AD3F9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7a9e60ce3d1cc32797da1f44ff0782a98e6210e","datavalue":{"value":{"entity-type":"item","numeric-id":1082819,"id":"Q1082819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$31D23059-1D3B-4DAD-A89C-8706100706C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106664$2D21CCC1-BD58-4E5D-BCB9-AF1D3A22B97E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"daf2f64771adf52056018c0a2635c3204f0b8ec9","datavalue":{"value":"https://doi.org/10.1016/0022-0000(88)90027-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1106664$0AC614B3-F5A8-4653-90E0-61443C17BE4C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d867c7c6f4b5a5b06afc25e514ada240fecc26a1","datavalue":{"value":"W2005390858","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106664$E2C3D981-B8CB-4FC4-97A0-A1EB4CA2BF0F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dc563087439fec342cb7cb4f34d8fdadf81f6b0","datavalue":{"value":{"entity-type":"item","numeric-id":3768419,"id":"Q3768419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"079f5b65014c212bf083311439887a00fa7c5435","datavalue":{"value":{"amount":"+0.8020539283752441","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":"Q1106664$3A18085D-2186-43D3-99C5-1C119E59B492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba3efbac63ff16b8d4b9874703a9b84c1f425b1e","datavalue":{"value":{"entity-type":"item","numeric-id":4251082,"id":"Q4251082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aca2415b56471804b1ca86f0b321eafb512a4543","datavalue":{"value":{"amount":"+0.7892018556594849","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":"Q1106664$2E44E193-184E-46CB-99E1-C80D30C898D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a453761894a408c2632741908bd24f2fc41a00fe","datavalue":{"value":{"entity-type":"item","numeric-id":3771607,"id":"Q3771607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43e1b61248c2af3bca0ef172aaba5807605ef07f","datavalue":{"value":{"amount":"+0.7878434062004089","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":"Q1106664$E1205D29-3644-4F8E-9F3A-3DE89DC4D590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2d3b0620c9e2593dfc6861ff60dbe09d22a0d72","datavalue":{"value":{"entity-type":"item","numeric-id":3349963,"id":"Q3349963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d678aaf0bc0677705be65b57f7452a92dfb07d18","datavalue":{"value":{"amount":"+0.7862274646759033","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":"Q1106664$C4B261F0-5B27-474E-8A5C-27161C67FACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c2b5c98aa74dbd47a5ed1c12b31b5ad585147cd","datavalue":{"value":{"entity-type":"item","numeric-id":3746899,"id":"Q3746899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d4ddd6c89821a6f8ae2033779ce8a4b8a4f3107","datavalue":{"value":{"amount":"+0.7842086553573608","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":"Q1106664$01A332CF-EEF0-4CCF-B049-1EAF89D008B9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of parallel search","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_parallel_search"}}}}}