"Ny karazana famantarana tsirairay dia niafara tamin'ny fanolorana olana mahaliana iray hianarana."
Ny Vavolombelona dia kilalao mahaliana sy tsy misy dikany. Amin'ny lafiny iray, ambara ho tompondakan'ny fihatsarambelatsihy. Amin'ny lafiny iray, dia mendri-piderana be izy noho ny fahasarotana matematika. Ny fitsipiky ny Vavolombelona dia sarintany amin'ny alalan'ny marika eo amin'ny takelaka chessboard, ary na dia toa tsotra aza izy ireo, dia betsaka kokoa ny zava-mitranga tsy hita maso – hany ka misy ny sasany mandalina ny tena mahasarotra ny olan'ny Vavolombelona eo amin'ny sehatry ny dokotera.
Erik Demaine, mpampianatra momba ny siansa informatika ao amin'ny MIT, dia mifantoka indrindra amin'ny fikarohana sy fampianarana, ary matetika no manambatra ny roa amin'ny alàlan'ny fanerena ireo mpianatra hamaha olana misokatra amin'ny vondrona. Mba hanaovana izany, Demaine dia mampiasa fomba fikarohana tena iaraha-miasa antsoina hoe supercollaboration.
Araka ny voalazan'ny tranokalan'i Demaine – mifamatotra etsy ambony – ny supercollaboration dia fomba fikarohana manavao izay ahafahan'ny mpikaroka mamaha olana sarotra tsy misy ahiahy momba ny mpanoratra na ny ego. Tena ara-bakiteny tokoa ny fiaraha-miasa, ao anatin'izany fiaraha-miasa tsara sy mahomby izany no laharam-pahamehana noho ny fandraisan'anjaran'ny tsirairay. Raha liana manokana ianao dia nampiditra horonan-tsary momba ny kilasy nampianarina tamin'ny fampiasana modely supercollaborative eto ambany aho.
Demaine dia iray amin'ireo mpanoratra lehibe amin'ny taratasy 2018 antsoina hoe Iza no manatri-maso ny The Witness?, izay manome tranga fakan-tahaka amin'ny fikarohana supercollaborative ary miaraka amin'izay koa ny extrapolation izay mahatonga ny The Witness ho lalao mendrika hianarana ho an'ny mpahay matematika sy mpahay siansa momba ny informatika: voalohany indrindra, ny fahasarotany.
Ho an'ireo izay tsy mahalala ny teny hoe "vavolombelona" ao anatin'ny tontolon'ny matematika, dia sanda manokana adika amin'ny fanambarana misy izy io - amin'ny ankapobeny, dia sampana ampiasaina hanavahana ny zavatra efa misy, ny zavatra misy amin'ny tranga iray farafahakeliny, ary ny zavatra efa misy nomena. fepetra. Raha ny momba ny The Witness, ny vavolombelona amin'ny litera kely dia misy ifandraisany amin'ny fomba famahana ny piozila tena izy - momba ny paikadin'ny fahombiazana inona izany, ary ny lalana amin'ny alàlan'ny grid iray maneho izany.
Iza àry no manatri-maso ny The Witness? Raha ny fantatra dia tena sarotra ny milaza izany – ary izany no mahatonga azy ho mahasarika eo amin'ny lafiny akademika.
Mandalina lalao matetika ny ekipan'i Demaine mba hitadiavana algorithm mahomby, ary hamakafaka ireo olana tsy azo fehezina amin'ny fikajiana ho fomba fitadiavana vahaolana vaovao izay matetika avy amin'ny sehatra ankavia.
“Amin'ny ankapobeny, tianay ny hanandrana hamaritra ny sisin-tany eo amin'ny lafiny mora sy sarotra amin'ny kajy amin'ny piozila The Witness,” hoy i Demaine. "Ny piozila sasany dia mampiasa karazana famantarana iray, fa ny hafa kosa mampiasa karazana fanondro. Te-hahatakatra hoe iza amin'ireo fangaro no mahasarotra ho an'ny solosaina vaha-olana, ary mety ho sarotra ho an'ny olombelona [koa] izany, ary izay tena mora ho an'ny solosaina ny vaha-olana – na dia tsy midika aza izany fa mora ho an'ny olombelona izany. ”
"Tsy fahita firy amin'ny ankapobeny ity farany rehefa mamakafaka piozila toy izany, noho izany dia nahafinaritra ny raharaha monominoes," hoy izy nanampy.
Iray amin'ireo tanjona fototra amin'ny fikarohana sy fampianarana nataon'i Demaine ny fanamafisana ny hamafin. Sarotra ny fahaiza-manaporofo ny hamafin'ny: ny fitadiavana porofo amin'ny maha-sarotra ny olana amin'ny alalan'ny fanovana na fampihenana azy ho endrika olana manokana. Teny an-dalana, hita ireo algorithm mahaliana azo ampiharina any an-kafa - ny fifanolanana amin'ny sarotra amin'ny kajy dia miteraka vahaolana amin'ny fanatsorana, izay midika fa tonga amin'ny zavatra mora kokoa ampiasaina amin'ny alàlan'ny fanasarotana bebe kokoa ny ao ambanin'ny sarony.
Adam Hesterberg dia mpikaroka iray hafa nomena anarana hoe Who witnesses The Witness? Na dia mpianatra PhD amin'ny matematika tao amin'ny MIT aza izy tamin'izy nanomboka niasa tamin'i Demaine, dia mianatra siansa momba ny informatika amin'ny ambaratonga postdoctoral izy izao. Ho azy, ny Vavolombelona dia toa "mahaliana amin'ny kajy".
“Mbola tsy nilalao ny The Witness aho raha tsy nanapa-kevitra ny handamina ny fahasarotan'ny kajy, na dia manao piozila lojika mitovy amin'izany aza aho”, hoy izy tamiko. “Tiako ny lalao board, na lalao fitantanana loharanon-karena ara-toekarena alemana toa ny Gaia Project na izay rehetra nataon'i Vlaada Chvátil, izay nomeko anarana ny tranoko. Manoratra taratasy amin'ny lalao hafa indraindray ny vondrona mpikaroka ataonay.”
Nanomboka niasa tao amin'ny Who witnesses The Witness ny vondrona Demaine? tamin'ny 2016, roa taona talohan'ny namoahana azy ho taratasy FUN (avy amin'ny International Conference of Fun with Algorithms) tamin'ny 2018. Hifarana amin'ny farany amin'ny taratasy diary feno niara-nanoratra tamin'ny akademika 10 avy amin'ny departemanta telo ao amin'ny MIT izy io, ary ny iray oniversite any Alemaina.
Tsy mifantoka fotsiny amin'ny The Witness izy ireo, na izany aza: Ny vondrona Demaine dia miady amin'ny rafitra kajy amin'ny lalao hafa isan-karazany, ary matetika dia mampihatra porofo mitovy amin'ny hamafin'ny hamafin'ny fahasarotana sy hahitana algorithm hafa.
"Ny fahasarotan'ny kajy amin'ny lalao sy ny piozila dia lohahevitra tiako indrindra izay nianarako nanomboka tamin'ny taona 2000 tany ho any," hoy i Demaine manazava. “Ny taratasiko voalohany dia momba ny Clickomania, izay isika notsidihina vao haingana. "
Demaine dia manondro ny taratasiny momba ny Tetris dia feno NP - midika izany fa azo voavaha amin'ny alàlan'ny kilasy faneriterena amin'ny algorithm fikarohana mahery vaika - ary Super Mario Bros dia feno PSPACE, izay sarotra kokoa - toy ny sasany amin'ireo zava-bitany malaza indrindra eo amin'ny sehatra hatramin'izao. Inona anefa no mampiavaka ny Vavolombelona? "Rehefa nivoaka The Witness, dia toa kilalao voajanahary tokony hatao izy io, manolotra karazana piozila / famantarana isan-karazany ao anatiny," hoy i Demaine manazava. “Satria anisan’ny filalaovana an’ilay lalao ny fahafantarana ny tena dikan’ireo fanoroana hevitra, dia nampitandrina ny antokon’olona hianaranay Ny Vavolombelona aloha izahay, ary nampirisika an’ireo izay te hisoroka ny mpandroba mba hilalao ilay lalao sy hamantatra ny zava-drehetra ho an’ny tenany.
"Herinandro vitsivitsy taty aoriana, dia nitsambikina tamin'ny famakafakana izahay, ary ny karazana famantarana tsirairay dia niafara tamin'ny fanomezana olana mahaliana iray manontolo."
Jeffrey Bosboom, izay mpianatra PhD ao amin'ny MIT hatramin'ny 2011 ary niara-nanoratra hoe Iza no vavolombelona Ny Vavolombelona?, dia nihaona voalohany tamin'ny The Witness rehefa nobeazina nandritra ny iray tamin'ireo fivoriana supercollaboration isan-kerinandro nataon'ny ekipa. "Midika izany fa nanimba ny ankamaroan'ny karazana piozila aho," hoy izy tamiko. “Saingy tsy mahatsapa aho fa mampihena ny fahafinaretako rehefa nilalao izany; Ny piozila fampidirana isaky ny faritra dia didactic ihany, ary mbola nahafinaritra ny nahatsapa ny fiovana avy amin'ny fahalalana mazava (afaka milaza amin'ny olona ny dikan'ny marika) ho amin'ny fahalalana implisit (mijery piozila ary mahafantatra avy hatrany izay tokony ho vahaolana. ).”
Ny iray amin'ireo zavatra tsy mahazatra indrindra momba ny piozila The Witness dia ny sasany dia Sigma_2-complete, fanamarihan'i Demaine. Ho an'ireo izay somary tsy matoky ny dikan'izany - izay azo antoka fa izany! – Sigma_2-completeness dia manondro teboka iray ao amin'ny ambaratonga polynomial, izay manasongadina isan-karazany amin'ny ambaratonga samihafa amin'ny famahana olana.
Ny fahafenoan'ny NP dia misy ny famahana olana amin'ny fampiasana herisetra; Sigma_2-completeness dia dingana iray avy amin'izany; ary ny fahafenoan'ny PSPACE dia mbola sarotra kokoa, misy ifandraisany amin'ny fotoana polynomial (ny fotoana ilain'ny solosaina hamahana olana) sy ny fahasarotan'ny fotoana (ny fahasarotan'ny kajy amin'ny habetsaky ny fotoana ilain'ny solosaina iray hampandehanana azy. algorithm manokana).
Somary sarotra ny famakafakana, saingy araka ny piozila nataon'i Demaine The Witness – fara faharatsiny, ireo izay misy “antibodies”, izay ho azoko ao anatin'ny iray minitra – dia miorina mafy eo afovoan'ny telo, misy ho “ambaratonga iray. Miakatra avy amin'ny fahafenoan'ny NP mahazatra, raha mbola ambany lavitra noho ny PSPACE-fahafenoana mahazatra amin'ny piozila izay mitaky fihetsehana be dia be - toy ny sliding blocks na Rush Hour".
Ireo famantarana voatondro ho "antibodies" ao amin'ny taratasy, izay fitsipika lojika manafoana ny fiantraikan'ny fanoroana hafa ao amin'ny faritra mitovy amin'ny piozila iray, dia manana mari-pamantarana "ilaina" izay mitaky fomba fijery kely kokoa amin'ny famahana olana. . Mampitombo ny fahasarotan'ny kajy izany ary manome olana maro mahaliana izay azo ovaina ho iray hafa mba hahatongavana amin'ny algorithm vaovao mahomby (ny fanovana olana iray ho endrika hafa dia kalitaon'ny Sigma_2-fahafenoana ihany koa).
