## Size of search with 30000 binary decisions

How many decisions went into designing the Boeing 747 or the Internet as we know it?

Suppose that it involved 30,000 decisions compared with what we could do at the time of Newton.

I don't know how realistic that number is for a 747. It may be too small. I am sure 3000 would be too small.

How many different types of component are used? How many options had to be considered for ways of using each component?

I am sure 30,000 is too small for the number of design decisions behind the internet as it was at the beginning of 2010.

It is often assumed that the problem of handling enormous search spaces can be solved using parallelism.
The aim of this little tutorial is to show that that is an illusory hope.
Much more creative transformations of combinatorial problems are required to make them tractable.

(An example related to machine vision is here: how to see a changing 2-D array of black and white pixels.)

How big is a search space with 30000 binary decisions?
How much more tractable can we make it if we use parallel processing?

A search tree of depth 3000 with two options at each choice point has this size (2 to the power 3000):

```    2**30000 =>
```

In Pop-11 this prints as:

** 794090351913296032413251784349270251399372812520869285560834338579193731744390878350 92031795308921919871559266239782831054899213844249232635733913637345223822317420280 63376725759936388639366060309563838895747548705834901470733791335653266902911839098 78244710921874319696676015799834022804373455377618705111862070943957994709350840140 16317120739168794456388493464371873680002881684348843338479257622368476288554189076 50698624898277065152326488047315941120701839655677173867549336208651066198963223290 58986784648513281167158518824955846996653467935662266301451746325522032547487024032 63696871715275750531143522989453935244032544880267135327056198782453362702520627747 83554202422698010972274190731058780728665028820297377514920071911925316084153056162 48012638825658080560866857409831665260808477138195327918180715712471349561353542496 42150876305790964166694126309639862665522557183281600931171716371766504612959055677 98132566281830354760366845352847955988129319896463854644608371823052534475141787679 87278651415911492173970800261725527013238891881141097743589539624845176865418731956 32386862839695232365989375750740751348320470155199672961178650596724086541434983001 65797510261969248336086014507694880004991778986415235204301660350334495307361712887 96028463267713978704891739364328745930547424898010567315982813166882301710108298658 50623923659482050909591130718810418279109553509537045443706104729510705845671221531 34386488507931897347896476243074931121650906482288868176150253025211895156520637042 14187793878216268997414253585681140935079799995693584130487046280856149589833350847 28258316088415416297747551257497271596217420646156983627543327038900812878501922794 65994174027123241887841355700008797695827617585094166714681343934267814915983302899 63720848689537900347826040479437019091527923182073387037961198448689230538554789165 80359574449157732345128956266533243298222368383478333476874257574618603852298113468 53592062462047018996231044691628755849499236009150479879605728979573172369124457634 18510298126460356608337097897079910108902783655444038281947211860145840191864392806 98764065424060711186158066250858244568548639796458999666371532095522123966404379437 72545570483804997716243538941179327354233526696713020947472416870994670783011051712 32787077443658331912503131642680307202606914264554400573301412883114676597949459813 98254591058649075839658818826210652269837026180612284427564317691229646136173751936 03363395778677616863258776074909714481159472483656638636883905929561817009023225704 49493164958024448306744289544811659020056786243984350875733887430566606402033858661 54942308699503776109014269525585552907546467310847123153772916852214866838027831731 17977276188840040275281110684283769640407214107271547786283887632689107752753390160 52308338609774766236127017768941870552765652258645819186267384707206156973910449229 05201986830389021769823107538498093953208866395176345361582008064712595210495397279 43187963197268440224844191407585128461076820807297787167383627575728041411301362585 40949341587030842321219352114949326011694597040411237763949377724389127175662138869 93836600924833782471378374042681811404833707993301624269828276571522512441979410171 92462061402979725739794687203586057387049201328340740887613387447373950100364897993 31670344160990441082227095677405852519689581345092546065599277645878569635609653871 93296356474352396373809874988604399743953813036409797069810476644490928377414234377 50637398558006767405145577627845832442613424523401175851345000125719849355699508871 87280972287177172892057463505775453970480825639825802165718163164665385821814229484 31888253322709430947737190521090240647411717724778056035082570366743002947726830427 59362219623448371538133982379930047191809206227921208700106982255244604098915930509 97737448688181026564241331476818392125226557568763585568935836448878456978207376809 53100837231714114942795854070161581649456215057636172078934099442626184029659318730 79670095015733617746877300750509712879507227799458469597736523821060866640083030773 50659370349895827145950963543071451599616595731686075545265988738075488372646575456 20840097578076767428415409152314527463889301553687779693021491966124270152578662246 09809635545481432467055079781718688694625568390291242476874334496646167840811344038 61691203626267789875235313761793246442693853306814959439733041879379512145117829661 97808891169462697207564531977971756304670288318117676949240264433098166200344156712 99267529082859608565046302314480222041155660138589746509861360513578781207262965589 56749465137341318242500910483973019014993794762208952592070895201484982770302533543 81840572146376096017597978232989345253940900479845912626553219802116107284876901265 12120377208077136664007624578448120627230396424410042374844009670652260318316136052 06490707343570162975672492058473615892892427893488371966798874671361890688241726596 63383744392875406312356521838055857825771550161129205198703277323808366371937666328 02136294403009176925679245705047676377488689151940988044538779620569126246914623230 62255087383301621638656385132879925923849920999955427514403682964052374802140172802 31222443073479926715765278517546131767098618681413119269313543041728231262463393845 47648330807215813145604886297539405314289438215407049391797179642618840408152005708 84000703906356012935992573283091741189275777280981857509678464456571576033089445012 63911623642085448627247386856234808312136732358099093804771614515846438435685349380 96246268595494491365840517011400827280642612038747802019218876411298166730081425354 98992665551226042407768357585203440769300870479172059563374251386970726252462601737 74931642873048194600430786640396410367752795424172094351656755678250460328863164061 29631936546931605479637395114227232190652680872356798895146260947715560593392445186 98423695657081535250386642568473128602962137198784398387393420200183409849377034075 58849334211973543199961629277988229530018868666269056340796452764443439538826364599 87016836014105836047428179943564602344815587492558221783493716856715822173632068059 94755128526956362233552299148974573428225580186290153930787762189076253425939595599 42654984413980615421380345652513179482804902603339107012847026373782175803005197788 21654757373607001758665360274942735667175469786830514617316799788829828488595159136 08278142078717394097758903664369944598890011146350409111850595773153112288101365609 67138485032072138014294503476522617017037974527108168936574038945754370349343093591 18706773291294149609820409223114512957520662826447436712867350827763314329955554198 05649959332461711099741847359169824375092903457973704337342229533279962446048343501 41071650580596806627565092941861278967803395889282955455670486481377773888246582428 65273549421647865095857398123831625977971274399024570969728319426236983475449696817 50151301392309281116048870102098122321763813487023833078598777736210790087022056611 76253697324846850795739059714120108692048519296751052025264624404508433314775913375 04677466560247802932519058064669736932026506218065518053804099470058672554881957334 23917194547012832811111815421924870927677196446893414143206527983595680475847902050 61756346763147957743777567816191477876441278643263959557195416354246250053309316543 36931776693662159112848110480538382283610794193466885074933882258128230814880496958 68938848061601932541077612716336386540035682211113443839443242839143213583929266155 38031068629318350062881736272613241001739908652863495338300630915575679568306962840 20826665435848602925945339374112474445787390743846224660527423380047536181832382852 74900448263913248801242377263287256761183795650972773866531912583343548683718388466 25113385609586548376538436059812673545692716666822568764363600040857208784383652925 20427632066423329003200404292501117164412280016866913720423748205122496830626503634 35750973101318199246425962843161716403651548829167678217031782652564368159165599008 19921528322815327888073851365442813435812259574397475706264191444980204428350125203 33597010650792505163588284469813745780712765859388127933246124890834158661340828624 38947385892474775526242478069226894881309443860400965504080647369730737386982680881 98092416414012027361333304334994010524883238094272801132316579691814978984550753955 95987717599255810574111896611381295446449094360605719953456587602255949355196532488 35909746306453115968109982758875433937617860357220699310411672400586567751929639815 99487154731785340238397487769689309593594300504676823389534600037197283165791876918 78697698768262029532555154453385626292655405747586784964721828435123748874036892336 46799383331356635109901206213370833065983994583533440800354088371046668558700301716 65992830170749473015844149888650047860282932854997704911804053060648018355377326172 78174051627839185610787636744236037208733359089934980863639140305262357999304049578 25380586743507238387211823939250953257693796574768103741118924445642776721896922665 99237363386859363652293748525067609774849497180967047791392020253858860075395310056 59537317072283913313695763253184409898181120428466758352325450311576982995045335286 929880973682790673015037574198678081581095988135833790694215909376

That's 109 lines, about 9030 digits.

Using parallelism to save time?

Suppose you had a million million workers (a British billion workers), each taking a decision every milli-second,
how many years it would take them to explore that space completely?

They could take this many decisions in a year, roughly:

```    1000000*1000000*1000*60*60*24*365 = 31536000000000000000000
```

So this is the number of years required, roughly (dividing the number of decisions to be explored
by the number of decisions in a year):

```    round((2**30000)/(1000000*1000000*1000*60*60*24*365))=>
```

Which Pop-11 prints out as:

** 251804398754850340060011347142716340499547441819149316831822152010145145783990004550 64698057873199492602599970268830172201578898352438239673938962974805055752891115005 27453299644830158751701566561886047341370988300936993109694885634085891331466209759 88788911378067706651660329718364416160696808529178939977125212754933407759180251185 99796144323683661357302287374547144114663521589405391723262067992887010492311703791 38349386383268983115273493165688718011384398673159935904220362826183113330467790236 74209406598336276372132965127142265029380221948142524829227469027626215292835814317 80725796459689164932503653915986153996712501547522556864236491242533410293797763745 50847984025462332246408609440340810733341269920185621992300885309463887647181968595 40846219820414155428991266301950680257739877326926473845186680527800402575264314591 71153880107112812077211480945471798156241297939904109884313710163548485734702896904 48418495142640269774342606973886338149457546897661039651385201618167343504294072704 17072124370849661394587392269699875384715528881640378533609062539588145885787269138 86474778931917564804030116612994911005936222144596547742636558408398048751089225964 50341676262674165504847163402998122781897443869360488078482261653454621799645393482 99095783633851464581713514511773448100757047468927754729827122389295504093768486383 34165374067567875098170703551119488292462440864262127550642473595101060960702442139 56870398436051464151413139346484947717418476180330057133482449589425385323604971157 45239660666608405947937041345028266405086187213246316631940336847049768388455527285 41431480241126146720493262067953219050043575801039124691636011871797568771721817223 06568421495155771780771612030697868371330421608667607405720872632631854044895770833 21829289919310597522775888026204026855507332312935498172869482004277406943986171095 19393573835983552874533535092127487093550979319976640498755155243093164590404018730 50986828533119932456947946693185171185153233133292262772579188539945830913598572309 16574802805194177006702529774568718324740862397083979668298836840482572359165522833 26599462653494644592262197568131102412654946663007039468027502567073225509387487137 78711812050927510691350690937715413290916262904843043172080294543060207630330749528 26226242213235138226947974265182745815134105233559868269058033004539154172358403035 88994987017582786605675678217342292069329346201361074463332165680882054203505121745 31761604445293511181906004589963760299708102639414205554567448607801184997787679383 71858563216014855500616530170221860419855652664885956010823784700205037545038641128 09152178050324637274547903832314038846888149198010883800663659580230487962337592507 35025772510413508458676151282433970586126082606313910383778503181344846446205412912 39316444257285250582232057892231694112368611193127162349780373131407330344339944580 49594744682391242316661310102263474744168209790454193734646755474604450536052573972 42258993910853767194585296615799444590650945207793565184989734771603260214136657339 36120415267323326459037085272371044524256277600333345308203125863898125055702098829 88913178882811321179407145498059935123298359967434558685257571211162643468410518192 51795427892877893753105874937717547370322552425272939144981414081485905029288717019 69707744850643848643527110501460506253072546088626504967528943951635771700789464063 90568352509624681752222816777208396671725587593990930070335640742164804787358648648 37213786960301486366421098943380844889210243697171859415063736721752869531868185207 97590364119475257766380474221770501639548714370822489271219610338871570846592538522 42481054452913949438019149708615626790782508157273609853844041846379693983931643337 00964681514284744906815697101702830793952690965221083428496633135224696885754671014 07197313764643907459487991970071788471976965236162983754736122668974650234084023595 10749884966931162779932728966946214373876273166424458421782756038377151201693086862 88581334035937854435209697092373703982593616121086526381829186904192309310021255318 84404924641646317588137672356377299467153917976815726644237058833737788043076666494 23148179089953312857818178954944992219650336616466190922444663865463048627783695537 19498235523047131046123503228601816557149152838118734930515707285846704667938655517 06523085878446153562669746880325103514299167081054971917723567313349667727396572064 30051018255156867455468205218788608670938067071955123334995010284467962392295838632 98854492986700789118799563138787487963329420388949057112462379665645224888147820138 75174234252074238407693084247835178530883369724191068173538462456077176170187256958 33916974932260304419583326431059533629484050126790307149465125508027684958421138148 50367953198908275197871519716656557783875696481611505065589805197441736529146415541 62382898066834780243427350348323698596173397987534364525240637579706332663699177637 18728990484803211032583879324599143146173119660429098553622297477108183146859990591 07729672248544259552790222509210957755418787782832631926857806830469662051913566473 43434515278824715131486677173033969407613496004552076203197514892203315196010962963 69616452014675268491807863558328935745528481317038660346687450228858520821430553603 96895082067229773321158322646353185348265296237762255641741875837968937217196856198 89650147103740491164381206647352784496853049619793841168720974269587638265185643395 68718805061544092030456426577953706339464970940543852677819512466973122284273639453 62838111553619511468112797124366066489295602498334538945718821794551676411111563088 21344706225020941910124415774100532968449033003288958511978136538232726487970129926 98798719835441462011805804997588917544315320720501044632057570927907933894236163134 60689984952730722184055490586703206554620966791082191430475095429894584155692683024 79205890302220172263567555355299698313978354007732242005134899860535074153151012834 72491544334085978944685955504181960150310397217868168550480864017137062258633423579 36014978441814382308291533467644787653734014298756412285481264858167117634967043398 00467760187391033179081779283667736373739719744511083818742948436414337083314179223 56245238588908109912918678859878608410326262875234369296311208261600131850268010460 49484638943939308015812202015139122167419923194707798901990360156275313447677308198 91006513850430426844799246468914873350738841687706243376411274661705071121290387369 88564968617475944322138033826903417369684796590280368130572691192844485777949991625 82035379658578814564250510281302166716616141180380338886627140673440929201533344177 46591184466153510622698454895728635329494198204583239579319580648554021577260382896 18553922685374431325331396797901217328704780533131327833482523617889958741833644859 41550465950547902427656455518718805802248628360928643762597767448705283953402364541 31833872841295434143851113046073732344547125027595076445522189794587389043322569955 53099219090831700531373370026040115643089966798817558354028609970988214521428181562 35628318924482433705136687615636015008887146822065423025686231440277356847692147810 19760652760975657284091773028261311176965118102135151618216174525493303042823408818 68897877588517236727478934492704045496081075165925913101596720051447948393362923815 12218346237208954563942196372570516959541728245011061984694914465413568878386763368 43270816863775346442503048172354257527915931700632116894800622412209288934528559790 51887071483167919223389693135658688800653192748878581728278992553137899406490031342 02443767578592276422483935620913392454904677430189695795448827809502643385918436977 66013587095355545662494411866846542605651888524534745645145837323485397223401315470 01875122275997763944868859734846738186736655462589601967390791489363650679979595676 43463861005334642631659184516901673377857775246342882331438276320751679613973396636 97282779395395167188744914650926470193953433799203347988657972682827361795778031141 61568216743662902044670805227499623742964313665143796203153282421670536665509298960 97665211393579561505450369250955652517983500082251435798213509922258421696264849259 38276060975543751752359994314189147286057028114028718132953021109123140977607395003 16493029050612641857348206600391302170498236331263572150024283260976337831224871244 27951457889160264641714832766166062736697455086442706733084914891633672423641721362 36653268108337492379537665765751976768651021168575817893966156900236735081154756410 44992121617131323008116910124838061134447710713050743083946790980846424139330250164 50627124165481364007025353390850338119182967322294135262785967920828180135095412333 98908987611414458114504441341124693387234904421465449264445106662559192211662957165 35385854315940345324658850167633830498567647404552798361175815912179102725576270349 05560011297513694067347677810830808348786580127452746341843968894362746701960949257 43715305283963482492139720934567146517533547873784913667275153616705598909784665989 97728742829420143218002837558684554088929952175598378929284633515302784143643870515 15581341030024071953860909200020424244730187857834461679453783076984076292188399063 58760812204553230372115600399501461237350837

That's still 109 lines, and about 9008 digits.

How does that number of years compare with the age of the earth?
Or the age of the universe?

If you increased the speed of the workers a million times, that would still only remove about six digits from the number.

If instead of a million million workers hou had a million million million workers, that would remove only six more digits.

So
Can we use parallelism to solve the problem of how to search a space of 30,000 decisions?

What other alternatives are there?

Maintained by Aaron Sloman
Updated: 14 Apr 2010; 9 Oct 2010