Математик вирішив 30-річну задачу на межі між математикою та інформатикою. Він використав інноваційний, елегантний доказ, який змушує своїх колег дивуватися його простоті.
Хао Хуанг, доцент математики в університеті Еморі в Атланті, довів математичну ідею під назвою гіпотеза чутливості, яка, в неймовірно грубому виразі, заявляє про те, наскільки ви можете змінити вхід до функції, не змінюючи вихід (це його чутливість).
Протягом десятиліть, коли математики вперше запропонували гіпотезу чутливості (не доводячи її), теоретики-комп’ютери зрозуміли, що це має величезні наслідки для визначення найбільш ефективних способів обробки інформації.
На думку довідників Хуанга, на думку інших експертів у цій галузі, є не лише те, що Хуан зняв це, але й елегантний і прямий спосіб, яким він це зробив. Його докази не були офіційно перевірені або опубліковані в жодному математичному журналі. Але незабаром після того, як Хуан виклав його в Інтернеті 1 липня, його колеги швидко прийняли це як факт.
"Всякий раз, коли є таке повідомлення", - писав у своєму блозі Теоський університет в Остіні теоретик-комп’ютерний теоретик Остін Скот Аронсон, "~ 99% випадків або доказ невірний, або в будь-якому випадку це занадто складно, щоб оцінити це стороннім особам. швидко. Це один з решти 1% випадків. Я досить впевнений, що доказ правильний. Чому? Тому що я його прочитав і зрозумів. На це пішло близько півгодини ".
Райан О'Доннелл, професор інформатики, який вивчає теорію чисел в Університеті Карнегі Меллона в Пітсбурзі, зазначив, що докази Хуанга можна підсумувати в одному твіті:
Що насправді довів Хуан?
Для простоти уявіть 3D-куб зі сторонами, довжиною яких одна одиниця. Якщо ви помістите цей куб у тривимірну систему координат (це означає, що він має вимірювання у трьох напрямках), один кут матиме координати (0,0,0), а один біля нього може бути (1,0,0), один над ним може бути (0,1,0) тощо. Ви можете взяти половину кутів (чотири кути), не маючи жодної пари сусідів: (0,0,0), (1,1,0), (1,0,1) і (0,1,1) aren ' t сусіди. Ви можете це показати, дивлячись на куб, але ми це також знаємо, оскільки всі вони відрізняються більш ніж однією координатою.
Припущення про чутливість полягає в тому, щоб дізнатися, скільки у вас сусідів, коли ви берете більше половини кутів куба більш високого розміру або гіперкуба, сказав математик з університету івриту Гіл Калай. Ви можете записати координати гіперкуба у вигляді рядків 1s і 0s, де кількість розмірів - це довжина струни, сказав Калай в Live Science. Наприклад, для 4D гіперкуба існує 16 різних точок, це означає 16 різних рядків 1s та 0s, що мають чотири цифри.
Тепер виберіть половину плюс 1 окрему точку на гіперкубі (для 4D гіперкуба, це означає, виберіть дев'ять - або 8 + 1 - різних точок із загальної кількості 16).
З цього меншого набору знайдіть крапку з самими сусідами - що там мінімум кількість сусідів це може мати? (Сусіди відрізняються лише одним числом. Наприклад, 1111 та 1110 - сусіди, тому що вам потрібно поміняти місцями лише одну цифру, щоб перетворити першу на другу.)
Хуан довів, що цей кут повинен мати принаймні стільки сусідів, скільки квадратний корінь з числа цифр - в даному випадку квадратний корінь 4 - що дорівнює 2.
Що стосується низьких розмірів, ви можете сказати, що це правда лише перевіривши. Наприклад, не так складно перевірити 16 координат на кубі (або "рядки") для сусідів. Але щоразу, коли ви додаєте розмір кубу, кількість струн подвоюється. Тому проблему стає важче перевірити дуже швидко.
Набір рядків довжиною 30 цифр - координати кутів 30-мірного куба - у ньому понад 1 мільярд різних рядків, тобто куб має понад 1 мільярд кутів. З рядків, що мають 200 цифр, їх більше, ніж десять мільйонів. Це мільйон мільярдів мільярдів мільярдів мільярдів, або 1, за яким слід 60 нулів.
Ось чому математикам подобаються докази: вони показують, що у кожному випадку щось істинне, а не лише просте.
"Якщо н дорівнює мільйону - це означає, що у нас є рядки довжиною 1 мільйон - тоді припущення полягає в тому, що якщо взяти 2 ^ 1 000 000-1 і додати 1, то є рядок з 1000 сусідами - квадратний корінь мільйона, - сказав Калай.
Останній великий прогрес в гіпотезі чутливості припав на 1988 рік, сказав Калай, коли дослідники довели, що одна струна повинна мати принаймні логарифм н сусідів. Це набагато менша кількість; логарифм 1 000 000 - це лише 6. Отже, доказ Хуанга виявив, що там принаймні 994 інші сусіди.
Елегантний і «загадковий» доказ
"Це дуже загадково", - сказав Калай про доказ Хуанга. "Він використовує" спектральні методи ", які є дуже важливими методами в багатьох областях математики. Але він використовує спектральні методи по-новому. Це все ще загадково, але, думаю, можна очікувати, що цей новий спосіб використання спектральних методів поступово матиме більше додатків. "
По суті, Хуан концептуалізував гіперкуб, використовуючи масиви чисел у рядках і стовпцях (званих матрицями). Хуан придумав абсолютно несподіваний спосіб маніпулювати матрицею з незвичайним розташуванням -1s та 1s, що "магічно змушує все це працювати", написав Aaronson у своєму блозі.
Хуан "взяв цю матрицю, і він модифікував її дуже геніально і загадково", - сказав Калай. "Це як у вас оркестр, і вони грають якусь музику, і тоді ви дозволяєте деяким гравцям, я не знаю, стояти на їх голові, і музика стає зовсім іншою - щось подібне".
Калаї сказав, що різна музика стала ключовим фактором доведення гіпотези. Це загадково, сказав він, бо, хоча математики розуміють, чому метод працював у цьому випадку, вони не повністю розуміють цю нову "музику" або в яких інших випадках вона може бути корисною чи цікавою.
"Протягом 30 років прогресу не було, і тоді Хао Хуан вирішив цю проблему. Він знайшов дуже просте доказ того, що відповідь - квадратний корінь н", - сказав Калай. - Але за ці 30 років люди зрозуміли, що це питання є дуже важливим у теорії обчислень".
Доказ Хуанга є захоплюючим, оскільки він просуває сферу інформатики, сказав Калай. Але це також примітно, оскільки він запровадив новий метод, і математики досі не впевнені, що ще може зробити новий метод Хуанга.
