#вычислительная_сложность — Public Fediverse posts

Сикофантия? Или ускорение динамического пересчета определителя от O(n³) до O(n)?

Всем привет. Хотел бы поделиться своими результатами и обратиться за ответным мнением. Представлюсь: Шевченко Максим Юрьевич. Работал мануальным тестировщиком (в том числе); считаю себя исследователем, в основном, в области математики. Лет 10 тому назад мне удалось вывести обобщение тождества Деснано‑Якоби, связанное с методом конденсации Чарльза Доджсона (более известного как Льюис Кэрролл). Тогда это обобщение показалось мне интересным лишь с теоретической точки зрения, и никакого практического применения его я не предполагал. Некоторое время эта работа «пылилась в сундуке», пока я ее, наконец, не опубликовал на GitVerse (там же Python код, о котором позже). В настоящее время, оказавшись без работы, я вдруг понял, что мой труд, как и я сам, снова пылится без дела и пользы, и почувствовал досаду. Дело еще в том, что будучи человеком без ученой степени, в академических кругах я часто сталкивался с так называемым «недоумением» в свой адрес по поводу моих научных изысканий. Работа моя была опубликована в нерецензируемом журнале. Так что до поры мне не удавалось осознать степень ее новизны и область применения. И потому в качестве рецензента я решил наконец обратиться к искусственному интеллекту (далее «AI»). LLM‑модели не интересуются регалиями, не затягивают ответ на полгода и готовы отвечать на вопросы до бесконечности. Конечно, с другой стороны AI может «галлюцинировать», а также выдавать желаемое за действительное, то есть заниматься «цифровым подхалимством»: сикофантией.

https://habr.com/ru/articles/1052218/

#линейная_алгебра #вычислительная_сложность #определитель_матрицы #большие_языковые_модели #сикофантия #галлюцинации_ии #роспатент

Сложные вычисления — в минимальном объёме памяти

У вычислительной программы есть два ресурса: время (циклы CPU) и пространство (оперативная память). Но как они заменяют друг от друга? Правда ли задачу, которая решается в полиномиальном пространстве , можно решить за полиномиальное время ? Как выяснилось, «конвертация сложности» между временем и пространством работает гораздо лучше, чем предполагалось ранее. Новые открытия математиков доказывают, что память можно использовать потрясающе эффективно. Вопрос приобретает новое измерение с учётом дерьмофикации интернета и программного обеспечения, где разработчики легко жертвуют памятью и производительностью. Возможно, в этом причина ожирения софта , на фоне упрощения интерфейсов и массового отупения пользователей .

https://habr.com/ru/companies/ruvds/articles/1011548/

#симуляция_времени #вычислительная_сложность #закон_Мура #ожирение_софта #теория_алгоритмов #временная_сложность #пространственная_сложность #O_большое #MicroQuickJS #ruvds_статьи

Моделирование физических экспериментов и превосходство квантовых вычислений

Утверждение, что «квантовые компьютеры» уже превосходят классические по возможностям вычислений нынче превратилось в штамп. При этом исходное рассуждение, стоящее за идей «квантовых вычислений», вообще-то, обратное: можно ли из наблюдаемой на практике сложности вычислительного моделирования сделать вывод о возможности разработки более быстрых, квантовых, аналоговых вычислителей? Это до сих пор не подтверждено, а из того, что конкретный способ вычислительного моделирования некоторых физических процессов работает очень медленно, по сравнению со скоростью моделируемого процесса, вовсе не следует необходимость наличия новых, превосходящих вычислительных возможностей за этими моделируемыми процессами. Проиллюстрируем ситуацию фарфоровым чайником, а также вспомним про симуляции вселенных.

https://habr.com/ru/articles/939040/

#квантовые_вычисления_и_компьютеры #квантовые_вычисления #вычислительная_сложность

Совместные конфиденциальные вычисления: как это работает

Моя основная деятельность — конфиденциальная обработка данных. Это такая развивающаяся область науки и техники, в которой часто возникает что-то новое, поэтому терминология ещё не устоялась. То, чем я занимаюсь, по-английски называется Secure Multi-Party Computation, а на русский переводят как совместные или многосторонние вычисления. Однажды я видел перевод: «многопартийные вычисления», – но, надеюсь, это единичный случай. Лично мне нравится вариант: «конфиденциальные вычисления», который использует википедия . Его буду использовать и я. Представьте, вы собрали какие-то ценные данные, зашифровали их и сохранили на диске. Таким образом, вы защищаете данные во время хранения (data-at-rest). Далее, предположим, вам нужно передать данные по сети с одного сервера на другой. Серверы устанавливают защищённое соединение и обмениваются данными – снова зашифрованными. Так серверы защищают данные во время передачи (data-in-transit). Пока всё знакомо и понятно. Далее вы собираетесь делать то, ради чего вы эти данные собирали, хранили и передавали: использовать их. Что-нибудь посчитать, агрегат какой-нибудь, статистику или даже модельку обучить. Анализировать зашифрованные данные —, затруднительно, поэтому вы их расшифровываете и… делате беззащитными. Во-первых, это странно: вы старательно защищали данные, когда хранили и передавали, и вдруг почему-то перестали. Во-вторых, это опасно: атаки, утечки, несанкционированный доступ, всё, что угодно может случиться, когда данные уязвимы. Ну, и в-третьих, расшифровывать не обязательно: существуют методы, защищающие данные, когда они используются (data-in-use). Совместные конфиденциальные вычисления – один из них.

https://habr.com/ru/articles/872410/

#алгоритмы #вычислительная_сложность #вычисления #криптографические_алгоритмы #конфеденциальность #математика #шифрование #шифрование_данных #информационная_безопасность #безопасность_данных

[Перевод] Исследователи приблизились к новому пределу скорости решения задачи коммивояжера

Целочисленное линейное программирование может помочь найти ответ на множество реальных проблем. Теперь исследователи нашли гораздо более быстрый способ это сделать. Задача коммивояжера — одна из старейших известных вычислительных задач. Она заключается в поиске кратчайшего маршрута через определённый список городов. Несмотря на кажущуюся простоту, проблема, как известно, сложна. И хотя вы можете использовать перебор, чтобы проверить все возможные маршруты, пока не найдете кратчайший путь, такая стратегия становится несостоятельной, уже когда в списке всего лишь несколько городов.

https://habr.com/ru/companies/first/articles/805233/

#проблема_коммивояжера #алгоритмы #вычислительная_сложность #линейная_алгебра #ILP

Меры сложности: колмогоровская, вычислительная и эффективная сложность, логическая и термодинамическая глубина

Это продолжение статьи «Информация об информации» , где я показал, что информация – физическая величина, не имеющая ничего общего с духом, сознанием, «информационным полем» и другими эзотерическими понятиями. Но среди философов и мистиков бытует мнение, что физическая и метафизическая информация – не одно и то же. Дескать теория информации изучает только цифровые данные , а информация как таковая – это другое. Ведь об информации можно говорить только при наличии источника и приёмника информации, а значит, её объективно не существует без субъекта, который будет её воспринимать и интерпретировать. Кроме того, ни количество информации по Хартли, ни количество энтропии по Шеннону не позволяют оценить смысл сообщения. Но значит ли это, что смысл, глубину или сложность информации нельзя измерить количественно и объективно? Пожалуй, пришло время разобраться, что такое сложность, как её можно измерить, связана ли она с упорядоченностью системы и есть ли у неё объективные критерии. Также мы выясним, насколько наши сообщения универсальны и можно ли прочитать их вне биологического или культурного контекста.

https://habr.com/ru/articles/794376/

#колмогоровская_сложность #вычислительная_сложность #логическая_глубина #эволюция #значение #информация #энтропия_шеннона #интерпретатор

[Перевод] Простая проблема приводит к слишком большим числам для нашей Вселенной

Исследователи показывают, что навигация по определенным системам векторов является одной из самых сложных вычислительных задач. Нечасто пятилетние дети могут разобраться в вопросах, связанных с информатикой, но и это может произойти. Предположим, например, что у девочки по имени Алиса есть два яблока, но она предпочитает апельсины. К счастью, её одноклассники разработали хорошую систему торговли фруктами со строго контролируемым обменным курсом: за яблоко, скажем, вы получите банан. Может ли Алиса совершить серию сделок, собирая и предлагая бананы или дыни, и получить свой любимый фрукт? Звучит достаточно просто. «Вы можете пойти в начальную школу и рассказать об этом детям», — сказал Кристоф Хаазе , учёный из Оксфордского университета. «Люди подумают: «Это должно быть легко». Но математическая задача, лежащая в основе дилеммы Алисы и называемая проблемой достижимости для систем сложения векторов, на удивление тонкая.

https://habr.com/ru/companies/first/articles/782118/

#алгоритмы #вычислительная_сложность #информатика