Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Мне кажется, что все-таки изменяет. Т.к. еcли эта задача... 18.06.04 11:51 Число просмотров: 3479
Автор: lime Статус: Незарегистрированный пользователь
|
>В римской системе счисления задача умножения (а
> уж тем более деления) двух чисел NP-полная (если мне ничего > не изменяет)
Мне кажется, что все-таки изменяет. Т.к. еcли эта задача NP-полная, то я (да и все здесь присутствующие) знаю точный алгоритм сведения этой NP полной задачи к полиномиальной, называемой, например, "умножение в десятичной системе". Т.о. мы только что доказали, что P=NP.
Кроме того, т.н. "римские числа" - это все же форма записи, а не система счисления. Система счисления у римлян - десятичная, просто каждый разряд числа записывается не одним символом, а несколькими.
>Для нахождения алгоритма быстрой факторизации нужно всего ничего: ВООБЩЕ не слушать то, чему >учили в школе на уроках математики. Забыть про всякие таблицы умножения и придумать новую >систему счисления (обязательно непозиционную), в которой эта задача станет тривиальной.
Хорошо сказано...
|
|
|