Чистая математика, физика, логика (braingames.ru): задачки для мозгов, не связанные с торговлей - страница 73

Новый комментарий
 
(1) Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти?
 
aharata:

(1) Если положительный ответ на какой-то вопрос можно быстро (за полиномиальное время) проверить (используя некоторую вспомогательную информацию, называемую сертификатом), то верно ли, что и сам ответ (вместе с сертификатом) на этот вопрос можно быстро найти?
нет, простейший и широко известный контрпример - разложение на множители большого числа, являющегося произведением двух простых чисел
 
alsu:
нет, простейший и широко известный контрпример - разложение на множители большого числа, являющегося произведением двух простых чисел
Хотя, конечно, есть квантовый алгоритм Шора, так что в контексте данной задачи этот пример, может, и не катит
 
Кажется, это одна из нерешенных проблем математики. Или я что-то напутал.
 
Mathemat:
Кажется, это одна из нерешенных проблем математики. Или я что-то напутал.
тсс.. сейчас кто нибудь решит, и заберем потом миллион баксов.. :-)
 
aharata:
тсс.. сейчас кто нибудь решит, и заберем потом миллион баксов.. :-)
Американский математик Джордж Данциг, будучи аспирантом университета, однажды опоздал на урок и принял написанные на доске уравнения за домашнее задание. Оно показалось ему сложнее обычного, но через несколько дней он смог его выполнить. Оказалось, что он решил две «нерешаемые» проблемы в статистике, над которыми бились многие учёные. =)
 
aharata:
тсс.. сейчас кто нибудь решит, и заберем потом миллион баксов.. :-)
Да чего там решать, сложность 1, щас забацаем))
 

Больше всего порадовало про эту задачу (классы - это P и NP)

В настоящее время большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в 2002 году среди 100 учёных, 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута.
 
Mathemat:

(4) Мозголяндия имеет форму правильного треугольника. Внутренняя граница делит ее на два равных по площади штата. Опишите форму и расположение границы, если известно, что она непрерывна и имеет минимально возможную длину.

Очевидно, что каково бы ни было деление, хотя бы одна из частей представляет собой угол исходного треугольника, отрезанный по кривой (или прямой) от остальной части. Несколько нудно, но достаточно легко можно показать, что наименьшую длину при сохранении площади 1/2 будет иметь отрезок, делящий 2 стороны треугольника в соотношении 1:sqrt(2) каждую (т.е. отсекающий равносторонний треугольник меньшего размера от исходного).
 
alsu:
Очевидно, что каково бы ни было деление, хотя бы одна из частей представляет собой угол исходного треугольника, отрезанный по кривой (или прямой) от остальной части. Несколько нудно, но достаточно легко можно показать, что наименьшую длину при сохранении площади 1/2 будет иметь отрезок, делящий 2 стороны треугольника в соотношении 1:sqrt(2) каждую (т.е. отсекающий равносторонний треугольник меньшего размера от исходного).
ИМХО там не прямая будет =) и можно это доказать совсем не нудно
1...666768697071727374757677787980...229
Новый комментарий
Причина обращения: