Лэнс Фотноу - Золотой билет. P, NP и границы возможного

Французский мыслитель XVII века Рене Декарт пользовался «бритвой Оккама» для доказательства существования окружающего мира. Самое известное изречение ученого – это, безусловно, Cogito ergo sum , или «Я мыслю, следовательно, я существую». В философском трактате « Рассуждение о методе » Декарт выводит факт своего существования практически из ничего, основываясь лишь на своей способности рассуждать о себе. А как обстоит дело с внешним миром? Может, все, что окружает Декарта, существует лишь в его сознании? Ученый отвергает эту идею, выдвигая более простое и к тому же более вероятное объяснение: все люди – так же как и он сам – живут в реальном физическом мире, который можно исследовать и пытаться понять.

«И, заметив, что в истине положения „Я мыслю, следовательно, я существую“ меня убеждает единственно ясное представление, что для мышления надо существовать, я заключил, что можно взять за общее правило следующее: все представляемое нами вполне ясно и отчетливо – истинно. Однако некоторая трудность заключается в правильном различении того, что именно мы способны представлять себе вполне отчетливо».

Современник Декарта Иоганн Кеплер изучал движение планет по орбитам и сформулировал ряд законов, касающихся их траекторий и скорости, однако не нашел простого объяснения тому факту, что планеты движутся именно так, а не иначе.

Исаак Ньютон применил принцип «бритвы Оккама» для описания поведения физических объектов. Его знаменитые законы движения выглядят удивительно просто.

1. Всякий объект в отсутствие приложенной к нему силы продолжает оставаться в состоянии покоя или равномерного прямолинейного движения.

2. Ускорение, которое получает объект, прямо пропорционально приложенной к нему силе.

3. Любые два объекта действуют друг на друга с равными по значению и противоположно направленными силами.

Добавив к этому простое определение силы тяготения, Ньютон сумел вывести открытые Кеплером законы движения планет. Простые объяснения – средство чрезвычайно мощное!

Несколько веков спустя Альберт Эйнштейн высказал гипотезу, что простые законы Ньютона перестают выполняться, когда скорость движения объектов приближается к скорости света. К подобной точке зрения склонялись и другие ученые; большинство экспериментов подтверждало правоту Эйнштейна. «Всё следует упрощать до тех пор, пока это возможно, но не более того», – метко выразился ученый. Однако полученные им результаты не означали, что ньютоновская модель мира абсолютно не верна: в повседневной жизни она давала прекрасное приближение. Законы Ньютона остаются актуальными и по сей день и отлично работают для простых процессов – например, если мы ведем автомобиль или ставим эксперименты в школьной лаборатории.

Теория Эйнштейна, в свою очередь, не выдерживает столкновения с мельчайшими частицами, которые, как выяснилось, подчиняются правилам совсем другой механики – квантовой. Современные физики пытаются состыковать общую теорию относительности Эйнштейна с квантовой механикой; если это удастся, можно будет говорить о глобальной «теории всего».

Простые модели не способны охватить все многообразие нашего мира, однако приближение они, как правило, дают очень хорошее. Найдите простое объяснение какому-либо факту – и получите возможность довольно точно предсказывать развитие однотипных ситуаций. В информатике в последнее время этот принцип проявляется особенно ярко.

Сегодня вы можете взять выписанный вам чек, сфотографировать на телефон и отправить в банк по интернету. Программа проанализирует изображение и вычленит сумму и номер счета, даже если чек заполнен от руки. Сотрудникам банка не придется вручную обрабатывать чек, если только это не было оговорено заранее.

Расшифровать номер счета в нижней части чека для программы никакого труда не составляет. Цифры строго соответствуют установленному формату, специально разработанному так, чтобы номер легко распознавался компьютером.

А вот сумма в 30 долларов выписана от руки. Откуда машине знать, о какой сумме речь, если почерк у каждого свой?

Рис. 2.1.Чек

Задача явно непростая. Взять хотя бы цифру «два» насколько по-разному пишут ее разные люди!

Рис. 2.2.Двойки