Первый признак псевдонаучного бреда на физмат темы - отсутствие формул (или наличие тривиальных, на уровне школьной арифметики) - имеется :)
Отсутствие ссылок на чужие работы - тоже.
Да эти все формальные критерии и ни к чему, и так видно, что автор в физике остановился на уровне учебника 6-7 класса. Даже на советскую "Детскую энциклопедию" не тянет.
Чего их всех так тянет именно в физику? писали б что-то юридически-экономическое
подробнее ...
:)
Впрочем, глядя на то, что творят власть имущие, там слишком жесткая конкуренция бредологов...
От его ГГ и писанины блевать хочется. Сам ГГ себя считает себя ниже плинтуса. ГГ - инвалид со скверным характером, стонущим и обвиняющий всех по любому поводу, труслив, любит подхалимничать и бить в спину. Его подобрали, привели в стаб и практически был на содержании. При нападений тварей на стаб, стал убивать охранников и знахаря. Оправдывает свои действия запущенным видом других, при этом точно так же не следит за собой и спит на
подробнее ...
тряпках. Все кругом люди примитивные и недалёкие с быдлячами замашками по мнению автора и ГГ, хотя в зеркале можно увидеть ещё худшего типа, оправдывающего свои убийства. При этом идёт трёп, обливающих всех грязью, хотя сам ГГ по уши в говне и просто таким образом оправдывает своё ещё более гнусное поведение. ГГ уже не инвалид в тихушку тренируется и всё равно претворяет инвалидом, пресмыкается и делает подношение, что бы не выходить из стаба. Читать дальше просто противно.
приводил в упомянутой выше статье: это SAT (задача пропозициональной выполнимости), в которой по заданной булевской формуле требуется определить, истинна ли она хоть при каких-нибудь значениях переменных. Эта задача исторически была первой из известных NP-полных задач (ее полноту доказал Стивен Кук (Stephen Cook), и проблему P=?NP иногда в его честь называют проблемой Кука). Несмотря на эквивалентность всех NP-полных задач, на деле сводить одну из них к другой бывает весьма неэффективно. Поэтому лучшие алгоритмы-рекордсмены, да и вообще алгоритмы, предназначенные для практического применения, разрабатываются для каждой задачи отдельно.
Машины, работающие за полиномиальное время с подсказкой, кажутся гораздо мощнее, чем обычные машины без подсказки. Действительно, им нужно всего лишь проверить данный ответ, а обычной машине нужно его сначала найти. Однако вопрос о том, нельзя ли каждую недетерминированную машину Тьюринга превратить в детерминированную, до сих пор открыт. Собственно, это и есть знаменитая проблема равенства классов P и NP.
Учитывая сказанное выше об NP-полных задачах, проблема будет решена положительно, если найдется полиномиальный алгоритм хотя бы для одной NP-полной задачи. Но пока таковых нет даже в перспективе; более того, нет даже субэкспоненциальных алгоритмов (то есть тех, которые бы работали за время, меньшее 2 cn , но большее полиномиального — например, за 2 √ n~). Такие алгоритмы существуют только для задач, которые подозревают в том, что они занимают промежуточное положение — и не полиномиальные, и не NP-полные. Такова, например, проблема изоморфизма графов: по двум данным графам понять, можно ли перевести вершины одного графа в вершины другого так, чтобы ребра переходили в ребра. Впрочем, подозрения могут и не оправдаться: например, одним из самых громких результатов последних лет был полиномиальный алгоритм для задачи проверки числа на простоту. Примечательно, кстати, что проверка на простоту оказывается принципиально проще, чем разложение на множители[Возможно, это покажется менее странным, если напомнить, что сложность измеряется от длины входа. А длина входа в данном случае — это длина числа в двоичной записи, то есть примерно его логарифм. И алгоритм, чтобы быть полиномиальным от длины входа, должен быть логарифмическим от величины числа, которое нужно проверить на простоту].
Теперь, когда мы поняли формулировку задачи, перейдем к ее обсуждению.
Первое: почему она так сложна? Конечно, можно сказать «потому что вот уже полвека пытаются и никак не могут», но есть и более интересные и глубокие причины. Я уже упоминал в сноске, что если рассмотреть «классы с оракулами», то для разных оракулов ответ получится разным. Переход от обычных классов к классам с произвольными оракулами называется релятивизацией. Большинство существующих идей и методов доказательства теорем в теории сложности вычислений выдерживают релятивизацию, то есть могут быть обобщены на случай произвольного оракула. Стало быть, все эти идеи и методы для доказательства (не)равенства P и NP неприменимы! Более того, в 1996 году Александр Разборов (наш соотечественник, лауреат премии Неванлинны) и Стивен Рудих (Steven Rudich) ввели класс так называемых естественных доказательств и показали, что нет естественных доказательств, которые бы позволили доказать, что SAT не решается за полиномиальное время. Под впечатлением таких результатов некоторые математики начинают склоняться к тому, что несовпадение P и NP может оказаться недоказуемым в рамках существующей аксиоматики. В 2002 году проводился даже опрос на эту тему. Из ста исследователей на вопрос «как вы считаете, равны ли P и NP?» 61 ответил «нет», 9 — «да», 22 — «сомневаюсь» и 8 — «наверное, вопрос не зависит от существующей аксиоматики».
Второе: что будет следовать из различных решений этой задачи. Если P не равно NP, все в порядке. Небо не упадет на землю, Запад не сойдется с Востоком, а пришествие Зверя будет отложено до лучших времен. А вот если P=NP, то начнется такое… Практика показывает: на деле «полиномиальное» означает «относительно легко решаемое». И если появятся способы относительно быстро решать NP-полные проблемы — могут возникнуть очень серьезные проблемы уже вне математики. Например, современная практическая криптография, основанная на RSA или DES/AES, окажется бесполезной. К чему это приведет, любой человек, знакомый с тем, как нынче хранится защищенная информация (номер вашей банковской карточки, пароль к вашему почтовому ящику и т. п.), легко может себе представить. Кроме того, это повлечет за собой серьезные изменения в наших представлениях об иерархии сложностных классов: целый бесконечный набор классов, которые сейчас считаются разными — так называемая полиномиальная иерархия, — «схлопнется» до одного-единственного класса P, и многие другие весьма правдоподобные предположения окажутся неверными. И все же, в отличие от гипотезы Римана, здесь нельзя сбрасывать со счетов вероятность того, что классы
Последние комментарии
29 минут 32 секунд назад
33 минут 47 секунд назад
5 часов 54 минут назад
1 день 17 часов назад
2 дней 1 час назад
2 дней 16 часов назад