Математичар је решио проблем стар 30 година на граници између математике и рачунарске науке. Користио је иновативан, елегантан доказ да се колеге диве његовој једноставности.
Хао Хуанг, доцент математике на Универзитету Емори у Атланти, доказао је математичку идеју названу претпоставком осетљивости, која у невероватно грубим речима износи тврдњу о томе колико можете да промените улаз у функцију без промене резултата (ово је његова осетљивост).
У деценијама од када су математичари први пут предложили претпоставку осетљивости (не доказујејући је), теоријски рачунари су схватили да она има огромне импликације за утврђивање најефикаснијих начина обраде информација.
Према речима других стручњака на овом пољу, Хуанг је доказао да није то само Хуанг, већ и елегантан и непосредан начин на који је то урадио. Његов доказ није званично прегледан нити објављен у ниједном математичком часопису. Али убрзо након што је Хуанг ставио на интернет 1. јула, његове колеге су то брзо прихватиле као чињеницу.
„Кад год постоји оваква најава“, написао је на свом блогу Универзитет у Тексасу из Аустин теоријски рачунарски научник Сцотт Ааронсон, „у 99% случајева је доказ погрешан, или је у сваком случају превише компликовано да би га оценили аутсајдери. брзо. Ово је један од преосталих 1% случајева. Поприлично сам уверен да је доказ тачан. Зашто? Зато што сам га прочитао и разумео. Требало ми је око пола сата. "
Риан О'Доннелл, професор рачунарске науке који проучава теорију бројева на Универзитету Царнегие Меллон у Питтсбургху, истакао је да Хуанггов доказ може сажети у једном твиту:
Шта је Хуанг заправо доказао?
Ради једноставности, замислите 3Д коцку са страницама дужине сваке јединице. Ако ставите ову коцку у 3Д координатни систем (што значи да има мере у три правца), један угао би имао координате (0,0,0), а један поред њега (1,0,0), један изнад тога може бити (0,1,0) и тако даље. Можете узети половину углова (четири угла), а да нема комшија: (0,0,0), (1,1,0), (1,0,1) и (0,1,1) арен ' Не комшије. То можете показати гледајући коцку, али ми то такође знамо јер су све различите по више координата.
Претпоставка о осјетљивости односи се на проналажење колико сусједа имате када узмете више од пола углова коцке веће димензије или хиперкубе, рекао је математичар са хебрејског универзитета Гил Калаи. Координате хиперкубе можете написати као низове 1с и 0с, где је број димензија дужина низа, рекао је Калаи за Ливе Сциенце. На пример, за 4Д хиперкубу постоји 16 различитих тачака, што значи 16 различитих низа од 1 и 0 који су четири цифре.
Сада одаберите пола плус 1 појединачне тачке на хиперкуби (за 4Д хиперкубу, то значи да бисте изабрали девет - или 8 + 1 - различитих тачака од укупно 16).
Из овог мањег сета пронађите поанту са највише комшија - шта је то минимум колико комшија може имати? (Сусједи се разликују за само један број. На примјер, 1111 и 1110 су сусједи, јер морате замијенити само једну цифру да бисте прву претворили у другу.)
Хуанг је доказао да овај угао мора имати најмање онолико комшија колико је квадратни корен броја цифара - у овом случају квадратни корен 4 - што је 2.
За мале димензије можете рећи да је то тачно само ако проверите. На пример, није тешко проверити 16 координата на коцки (или "жице") за комшије. Али сваки пут када коцки додате димензију, број жице се удвостручује. Стога је проблем све брже проверити.
Скуп стрингова који је дугачак 30 цифара - координате до углова 30-димензионалне коцке - има више од милијарду различитих жица у себи, што значи да коцка има више од милијарду углова. Са жицама дужине 200 цифара има их више од новемдецилиона. То је милион милијарди милијарди милијарди милијарди, или 1 праћено 60 нулама.
Зато математичари воле доказе: Они показују да је у сваком случају нешто истинито, а не само лако.
"Ако н једнак је милиону - то значи да имамо низове дужине 1 милион - онда је претпоставка да ако узмете 2 ^ 1,000,000-1 и додате 1, постоји низ који има 1.000 суседа - квадратни корен од милион, "Рекао је Калаи.
Последњи велики напредак у претпоставци осетљивости догодио се 1988. године, рекао је Калаи, кад су истраживачи доказали да једна жица мора имати барем логаритам н комшије. То је много мањи број; логаритам од 1.000.000 је само 6. Дакле, Хуанг-ов доказ је управо открио да су најмање 994 друге комшије вани.
Елегантан и "мистериозан" доказ
"Веома је мистериозно", рекао је Калаи о Хуангином доказу. "Користи" спектралне методе ", које су веома важне методе у многим областима математике. Али користи спектралне методе на нов начин. Још увек је мистериозно, али мислим да можемо очекивати да ће овај нови начин коришћења спектралних метода постепено имати више апликација. "
У суштини, Хуанг је концептуализирао хиперкубу користећи низове бројева у редовима и колонама (зване матрице). Хуанг је смислио потпуно неочекиван начин манипулације матриксом с необичним распоредом -1 и 1 који "магично чини да све то функционише", написао је Ааронсон на свом блогу.
Хуанг је "узео ову матрицу и модификовао је на врло генијалан и мистериозан начин", рекао је Калаи. "То је као да имате оркестар и они пуштају неку музику, а затим пустите да неки од свирача, не знам, стану на њихову главу и музика постане потпуно другачија - нешто слично."
Та другачија музика испоставила се као кључ за доказивање претпоставке, рекао је Калаи. То је мистериозно, рекао је, јер иако математичари разумију зашто је метода функционисала у овом случају, они не разумеју у потпуности ову нову "музику" или у којим би другим случајевима могла бити корисна или занимљива.
"30 година није било напретка, а онда је Хао Хуанг решио овај проблем и пронашао је врло једноставан доказ да је одговор квадратни корен н", Рекао је Калаи." Али током ових 30 година ... људи су схватили да је ово питање веома важно у теорији рачунања. "
Хуангин доказ је узбудљив јер унапређује област рачунарских наука, рекао је Калаи. Али је такође приметно јер је увео нову методу, а математичари и даље нису сигурни шта би им Хуанг-ова нова метода могла омогућити.
