Сложность компьютерных алгоритмов

[vlapay]

Sonic86 в сообщении #1021472 писал(а):

vlapay в сообщении #1021291 писал(а):

Вот именно, это направление меня интересует. Может кто-то знает, существует ли хоть один алгоритм, для которого доказано, что "не быстрее, чем за $O(n^2)$"?

Так я же Вам объясняю: пусть есть задача, у которой длина входа $=d(n)$, тогда время работы алгоритма $=\Omega(d(n))$ (за исключением каких-нибудь дурацких задач типа "вернуть 1-й элемент из массива длины $n$").
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

Не пинайте сразу. Математика не мой конёк, о том, что означают многие математические символы, мне приходится только догадываться.

Цитата:

Еще раз говорю: Вы не сформулировали вопрос нормально. Что такое "универсальный алгоритм-ускоритель"? $N$ - это у Вас что? Откуда берется $N^2$?

vlapay в сообщении #1021429 писал(а):

Если есть универсальный алгоритм, то мы можем быстро получить доказательство любой теоремы (решение любой задачи), если такое вообще существует в природе.

Бред, доказательство теоремы - $NP$-полная задача.

Порылся в интернете и теперь могу сформулировать понятней. Есть нерешённая переборная задача, одна из семи задач тысячелетия. Универсальный алгоритм - недоказанное утверждение, что есть не только Равенство классов P и NP, но и что степень полиномиальной памяти и времени не превышает двойку. Причём, существование универсального алгоритма позволяет решить не только часть переборных задач, как доказал Левин, но и любую задачу математики.

[venco]

Sonic86 в сообщении #1021472 писал(а):

Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

Насколько я понял, ТС хочет более, чем квадратичное время от размера всей использованной памяти. Кроме NP задач, я так сходу не смог ничего придумать. В матрицах вообще все алгоритмы максимум $O(n^{1.5})$ от количества элементов. С NP задачами, конечно, время будет экспоненциальным, но, насколько я знаю, этот факт не доказан.

[Sonic86]

(Оффтоп)

vlapay в сообщении #1021528 писал(а):

Универсальный алгоритм - недоказанное утверждение

vlapay в сообщении #1021528 писал(а):

есть не только Равенство классов P и NP, но и что степень полиномиальной памяти и времени не превышает двойку.

vlapay в сообщении #1021528 писал(а):

Причём, существование универсального алгоритма позволяет решить не только часть переборных задач, как доказал Левин, но и любую задачу математики.

А, понятно. Я пошел.
Лучше бы вместо "Левин" было написано "Ленин". Смешнее хотя бы.

venco в сообщении #1021548 писал(а):

Насколько я понял, ТС хочет более, чем квадратичное время от размера всей использованной памяти. Кроме NP задач, я так сходу не смог ничего придумать.

Проверка простоты числа вроде $O(n^6)$ Линейное-программирование вроде как долго работает.

[vlapay]

Sonic86 в сообщении #1021557 писал(а):

[off]Проверка простоты числа вроде $O(n^6)$ Линейное-программирование вроде как долго работает.

Мало ли что долго работает. Нужно доказательство, что работать быстрее и менее объёмно нельзя в принципе. А такого доказательства, как я понял, нет. Собственно, это меня и интересует.

[Sonic86]

vlapay в сообщении #1021570 писал(а):

Нужно доказательство, что работать быстрее и менее объёмно нельзя в принципе. А такого доказательства, как я понял, нет.

Sonic86 в сообщении #1021472 писал(а):

Так я же Вам объясняю: пусть есть задача, у которой длина входа $=d(n)$, тогда время работы алгоритма $=\Omega(d(n))$ (за исключением каких-нибудь дурацких задач типа "вернуть 1-й элемент из массива длины $n$").
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

[Dmitriy40]

(Порядок сложности для матриц)

Забавно смотрится комбинация:

Sonic86 в сообщении #1021472 писал(а):

Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

venco в сообщении #1021548 писал(а):

В матрицах вообще все алгоритмы максимум $O(n^{1.5})$ от количества элементов.

[vlapay]

Sonic86 в сообщении #1021576 писал(а):

vlapay в сообщении #1021570 писал(а):

Нужно доказательство, что работать быстрее и менее объёмно нельзя в принципе. А такого доказательства, как я понял, нет.

Sonic86 в сообщении #1021472 писал(а):

Так я же Вам объясняю: пусть есть задача, у которой длина входа $=d(n)$, тогда время работы алгоритма $=\Omega(d(n))$ (за исключением каких-нибудь дурацких задач типа "вернуть 1-й элемент из массива длины $n$").
Пример: вычислить сумму квадратных матриц $n\times n$. Это нельзя сделать быстрее, чем за $O(n^2)$ просто потому, что в матрице $n^2$ разных элементов и они независимы друг от друга; просто потому, чтобы написать ответ потребуется $O(n^2)$ элементов.

Сумма матриц делается в один слой, так как это параллельный процесс. Вам этот пример ничего не даёт, ведь $N$ это общее количество информации - транзисторов и памяти компьютера, а для квадратных матриц $N>n^2$

[patzer2097]

Sonic86 в сообщении #1021472 писал(а):

доказательство теоремы - $NP$-полная задача.

vlapay в сообщении #1021528 писал(а):

существование универсального алгоритма позволяет решить не только часть переборных задач, как доказал Левин, но и любую задачу математики.

venco в сообщении #1021548 писал(а):

В матрицах вообще все алгоритмы максимум $O(n^{1.5})$ от количества элементов.

venco в сообщении #1021548 писал(а):

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

vlapay в сообщении #1021590 писал(а):

Сумма матриц делается в один слой, так как это параллельный процесс.

vlapay в сообщении #1021528 писал(а):

Математика не мой конёк, о том, что означают многие математические символы, мне приходится только догадываться.

Мне кажется, что тема уже не очень подходит для раздела ПРР(М)

[Sonic86]

(Оффтоп)

vlapay в сообщении #1021590 писал(а):

Вам этот пример ничего не даёт, ведь $N$ это общее количество информации - транзисторов и памяти компьютера, а для квадратных матриц $N>n^2$

Вот опять зачем-то вылезло число транзисторов.

Не, товарищи, зачем читать бред? Пойду что-нибудь осмысленное почитаю...

[vlapay]

patzer2097 в сообщении #1021596 писал(а):

Мне кажется, что тема уже не очень подходит для раздела ПРР(М)

Да пожалуйста. То что мне надо было, я уже выяснил.
Спасибо всем участникам.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Пургаторий (М)»
Причина переноса: темы перенесена в соответствующий раздел как бессодержательная и ввиду бесперспективности дискуссии