Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[44.210.86.29] |
|
Сообщ.
#1
,
|
|
|
Доказали, что если для задачи есть полиномиальный алгоритм, то есть и линейный алгоритм.
https://arxiv.org/pdf/2005.05764.pdf А тут программная реализация преобразователя программы из полиномиальной формы в линейную https://arxiv.org/pdf/2005.02853.pdf |
Сообщ.
#2
,
|
|
|
scrum0fscrums, это какой-то вопрос, или что?
|
Сообщ.
#3
,
|
|
|
Это тупняк. Кто-то путает понятия "линейное программирование" и "линейное время/память" (а также "полином" и "полиноминальное время/память"). Плюс, как водится, кто-то не читает документы, на которые ссылается, в частности, в упор не видит фразу "If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size". В общем, революция отменяется.
|
Сообщ.
#4
,
|
|
|
AVA12
Линейное программирование решается за линейное время. Так что порядок. Чёрт его знает, может и утка. Архив не больно авторитетный ресурс. |
Сообщ.
#5
,
|
|
|
Цитата Линейное программирование решается за линейное время. Так что порядок. Переведите, пожалуйста, на русский язык ту английскую цитату, что я привел. Цитата Чёрт его знает, может и утка. Где утка? Откуда взялось утверждение "если для задачи есть полиномиальный алгоритм, то есть и линейный алгоритм"? Где и когда оно было опубликовано? Если у вас лично какие-то особенные нетрадиционные способы чтения и понимания написанного - это ваши личные проблемы, не надо обвинять других. |
Сообщ.
#6
,
|
|
|
Цитата AVA12 @ Где утка? Утка в том, что может и ошибка закралась. Что-то уж больно неправдоподобно. Тысячу раз уже и теорему Ферма доказывали и то, что P=NP и то, что P≠NP. И всё с ошибками как позже выяснялось. Добавлено Цитата AVA12 @ If an algorithm produces the solution x to a problem in polynomial time and space then the LP constructed is also of polynomial size" Это у них лемма. Далее доказывается линейность. Надо от начала до конца статью читать. Две статьи. |
Сообщ.
#7
,
|
|
|
Цитата Это у них лемма. Далее доказывается линейность. Это не лемма, это часть аннотации. В которой нет ни слова о линейном размере итогового алгоритма. Если эта самая линейность где-то хотя бы упоминается - приведите цитату. |
Сообщ.
#8
,
|
|
|
Цитата scrum0fscrums @ AVA12 Линейное программирование решается за линейное время. Так что порядок. Чёрт его знает, может и утка. Архив не больно авторитетный ресурс. Методы ЛП, например, симплекс-метод в худшем случае экспоненциальны. Что неудивительно - чем универсальнее метод, тем он более трудоёмкий. Задача ЛП принадлежит классу P. Добавлено Цитата However this LP will only have polynomial size if the algorithm terminates in polynomial time. Вот, собственно, и всё Если я правильно поняла, то каким-то образом автоматизировали написание программ, использующих методы ЛП. |
Сообщ.
#9
,
|
|
|
Любой полиномиальный алгоритм выразили через линейное программирование полиномиального размера. Линейное программирование решается линейно. Полиномиальный размер не отменяет линейность.
|
Сообщ.
#10
,
|
|
|
Цитата scrum0fscrums @ Линейное программирование решается линейно. Квадратичное программирование решается квадратично. Выпуклое программирование - выпукло. Динамическое - динамично. Математическое программирование - математично. Но вот нелинейное программирование, как ты его ни крути, нелинейно. Вот такая вот загогулина |