Главная | Настройки | NSFW
Тема:
Доски


[Ответить в тред] Ответить в тред

[Назад] [Обновить тред] [Вниз] [Каталог] [ Автообновление ] 25 / 13 / 17

А что если все мы допустили одну большую ошибку Anonymous No.334
Earth-Chan-ero-[...].jpeg (656 KB, 811x1081)
Сап, двачанский
Не спится, даже нейролептики не помогают.
Вот размышляю я и думаю, а что, если мы все обосрались в 1977? Обратившись, когда доверились криптографии с открытым ключом. Потом доверились RSA, потом PGP.
Ведь вся эта криптография с открытым ключом базируется на предположении, что одни вычислительные задачи "труднее" других. Что P =/= NP.
Да, обратное не доказано.
Да, большинство мировых учёных думает (вдумайся, анон, просто думает), что P =/= NP.
Да, абсолютно все, включая NSA, CIA, ФСБ, Сноудена, Ааронсона, Шнайдера, твердо убеждены, что P =/= NP.
Да, количество любительских и серьезных доказательств на эту тему за 40 лет превысило, наверное, число работ "ферматистов" лет за 400. Причем где-то P = NP, где-то P =/= NP, а где-то вопрос неразрешим на машине Тьюринга и машине с произвольным доступом к памяти в рамках ZFC. Качество этих работ, пожалуй, хуже, чем у "ферматистов"...

Но, если мы просто плохо искали? До 2000 годов тоже думали, что задача определения простоты числа может решаться за приемлемое время только недетерменированно. Потом появился AKS алгоритм.

Просто представьте, мы выстроили всю человеческую инфраструктуру: DNS-сервера, маршрутизацию, TSL, SSL, mesh-сети, freenet, цифровые подписи, блокчейн, https, RSA-шифрование, управление дронами и умным домом, электронные казино - только на предположении. Представь это, анон.

Что будет, если это предположение окажется неправдой, анон?
Предлагаю поразмышлять, что будет с сетевой структурой в таком случае. О web 2.0 точно забудем, ибо любой пользовательский контент можно будет заменить на вредоносный и подписать. Останется ли хотя бы. web 1.0? Или вообще провайдеры и хостеры разорятся, и нас ждёт куча изолированных локалок?
Anonymous No.335
>>334 (OP)
>DNS-сервера, маршрутизацию, TSL, SSL, mesh-сети, freenet, цифровые подписи, блокчейн, https, RSA-шифрование,
Фринет сюда как-то не вписывается.
Anonymous No.336
ммм, не понятно.
Anonymous No.337
>>334 (OP)
Интересная тема. Я так понимаю, что если задача равенства классов P и NP когда-нибудь будет решена, все современные способы шифрования превратятся в тыкву?
Anonymous No.338
>>337
Да, если не придумают более совершенные и стойкие к взлому алгоритмы. А это когда-нибудь случится.
Anonymous No.342
photo_2019-02-0[...].jpg (65 KB, 646x807)
>>335
Freenet уважаю, он намного более приватен, чем Tor и i2p даже, но эта сеть также использует в ключевых аспектах криптографию с открытым ключом (например, DSA). А значит, в случае, если когда-нибудь установят, что P = NP (хотя, еще раз, подчеркну, что большинство ученых/криптографов/военных уверены в обратном), она тоже будет скомпрометированна.
>>337
Да.
>>338
К этим алгоритмам нужно будет реализовать еще и специфичные устройства. Если проблему равенства классов решат, то это будет относиться к любому алгоритму на машине с произвольным доступом к ячейкам памяти.
Тут тоже выходы есть, например, передача на основе квантовой запутанности. Прослушивающий линию и подменяющий сигнал неизбежно нарушит состояние частиц на обеих сторонах провода. Еще бы технически это реализовать, пока, к сожалению, в роли нарушителей хорошо справляются обычные тепловые колебания молекул.

Вообще, не стоит серьезно относиться к этому треду, это типичный what-if тред. Я просто наткнулся в вики на статью о постквантовой криптографии и задумался: а ведь все "квантово" устойчивые алгоритмы основаны на P/NP проблеме, а значит, если наука пойдет еще дальше квантовых компьютеров (хотя необязательно дальше, эту проблему могут и раньше первого промышленного квантового компа решить), то и всякие хитрые алгоритмы типа "суперсингулярной изогении" тоже будут бесполезны.
https://ru.wikipedia.org/wiki/Постквантовая_криптография - вот здесь описано, как будет выглядеть криптография и мир после квантовых компьютеров.
Я хотел просто пофантазировать еще дальше, а если решат проблему равенства классов, как тогда будет выглядеть мир?

Мне вообще представляется откат назад в плане отказа от IoT и Web 3.0 / Web 2.0. В самом лучшем случае статические страницы, которые не позволят пользователям отправлять информацию или модифицировать себя. Вместо IoT будут изолированные локальные сети со стойким симметричным шифрованием (оно никуда не денется). В самом худшем случае, кризис ударит не только по Гуглу / Эпплу, провайдерам, хостерам, но и по огромной куче банков, так что государствам придется принимать срочные указы, что делать с обесценившейся электронной валютой (любой). От глобальной сети перейдется перейти к локальным (тем айтишникам, кого не линчуют толпы).

Устройства для обмена сообщениями будут наподобие FireChat в его версии до 2016 года: без шифрования (оно все равно будет бессмысленно). И еще только без Интернета.

На конечных устройствах вендоры (если они останутся в живых) будут принудительно делать симметричное шифрование всех данных на девайсе. Да, veracrypt и AES останутся, в любом случае. Под давлением правозащитников протоколы обмена информации будут включать обязательное удаление передаваемой информации из кэша после передачи. Устройства опять же поголовно зашифрованы. Опять же - принудительная смена IMEI (или его аналога для будущих гаджетов) и давление на государства, где IMEI менять нельзя.

Это, если что, просто размышления, не стоит относиться серьезно.
Anonymous No.343
>>342
>Я хотел просто пофантазировать еще дальше, а если решат проблему равенства классов, как тогда будет выглядеть мир?
Я думаю для большинства людей ничего принципиально не изменится. Уж точно интернет не разделитсяна локальные сегменты, к этому не будет никаких предпосылок. В конце концов, раньше интернет существовал вообще без всякого шифрования. Возможно, в самом начале будет пара резонансных случаев с кражей чего-нибудь секретного, или с кражей кучи денег, биткойн обесценится. Банки введут дополнительные уровни безопасности при работе через онлайн клиенты, на основе одноразовых кодов, которые нужно будет получать лично в оффисе. Вообще было бы интересно за этим всем понаблюдать.
Anonymous No.344
>>342
>Freenet уважаю, он намного более приватен, чем Tor и i2p даже
Ну хуй знает. Вот когда если в нём будут туннели и интегрированная поддержка работы через вышеупомянутые сети - тогда поговорим.
Anonymous No.345
>>343
Какие могут быть онлайн клиенты без асимметричной криптографии?
Anonymous No.351
>>345
C симметричной криптографией.
Anonymous No.366
photo_2019-02-1[...].jpg (149 KB, 881x1080)
>>351
Да, все ключи придется раздавать в оффлайне. Если банкам - норм., то как быть с "Вконтакте", "Фейсбуками" и т.д.?
Вебу 2.0 нормис придет каюк. Хочешь иметь свою страницу в Интернет - придется и хостинг держать на своем железе. И ограничить пользователей от посыла какой-либо информации. Только статика, только хардкор!
Anonymous No.450
6XdRAAudQl4.jpg (190 KB, 1080x720)
С позволения, цитата из Пападимитриу "Алгоритмы":
> Существуют ли задачи поиска, которые не могут быть решены за полиномиальное время? Другими словами, верно ли, что P != NP? Большинство специалистов полагают, что да –– трудно представить себе, что всегда можно избежать экспоненциального перебора и что существует (до сих пор не открытый, несмотря на многолетние усилия) метод, позволяющий решать все задачи из NP. Другая причина: поиск не слишком длинных доказательств математических теорем лежит в NP (проверка записанного формально доказательства полиномиальна), так что равенство P и NP в каком-то смысле означало бы, что математики не нужны. Есть и другие причины думать, что P != NP –– но вопрос о равенстве классов P и NP остаётся одной из важнейших нерешённых математических проблем.

У меня появился интересный контр-аргумент к первому аргументу. Допустим, у нас есть NP-полная задача о сумме подмножеств (множество зададим целых положительных чисел, общность не теряется, в Вики есть как обобщить на случай всех целых чисел). Возьмем один крайний случай, элементы "максимально близко" пригнаны друг к другу. Ну вот так: 1, 2, 3, ... , n. Или идут как члены арифметической прогрессии, то есть отличаются друг от друга на некоторый постоянный шаг d. Тогда в задаче поиска пространство вариантов (всех возможных сумм) будет квадратичным ((1 + n) * n / 2), а не экспоненциальным. Количество всех возможных подмножеств, конечно же, экспоненциально, а вот пространство поиска, уже нет, зависит квадратично.
Возьмем другой крайний случай: элементы "максимально далеко" идут друг от друга. Например, как 1, 2, 4, 8, ... n. То есть не ближе, чем члены геометрической прогрессии. Для этого случая пространство поиска будет экспоненциальным (количество всех возможных сумм будет таким же, как количество возможных подмножеств). Но! Жадный алгоритм (отсортируем по возрастанию и пойдем с конца) -- даст абсолютно точный результат. (Например, когда раскладывают любое число по степеням двойки (или любого другого основания), ибо любое промежуточное число выразится через их комбинацию).

Интересно, что в первом крайнем случае "снизу" (арифметическая прогрессия) можно применить динамическое программирование, и оно будет не псевдополиномиальным, а строго полиномиальным, так как пространство поиска полиномиально.
Во втором крайнем случае "сверху" (геометрическая прогрессия) жадный алгоритм даст 100% точный результат в 100% случаях.
Напрашивается вывод, что "умный" комбинированный алгоритм (GA + DP) сможет избежать экспоненциального перебора для любого множества.

Это, конечно, никакое не доказательство, просто контр-аргумент, приведенный к аргументу Пападимитриу. На таком же, нестрогом уровне.
Anonymous No.460
EQ-8jbLesA4.jpg (65 KB, 640x494)
>>334 (OP)
Как обстоят дела с квантовыми компьютерами?
Anonymous No.461
pW8Rpg9OpTo.jpg (121 KB, 604x604)
>>460
Для них есть два отдельных раздела:
1) Постквантовая криптография — криптография на обычных компьютерах, после того, как алгоритм Шора реализуют на уровне круче чем 15 = 3 * 5
2) Квантовая криптография — криптография с использованием квантовых эффектов.

Однако, если P = NP, то и алгоритмы постквантовой криптографии становятся ненужными и взламываемыми. Если же реализовать квантовый компьютер, то решение NP-полных задач на нем будет занимать в асимптоте столько же время, сколько и на обычном. Короче, созданный рабочий квантовый компьютер приведёт к пересмотру используемых шифров (с RSA и эллипитических кривых на Hidden Field Equations, например). Решение P = NP, если оно существует, уничтожит ассиметричную криптографию вообще.
Anonymous No.470
азиатка-5075149[...].jpeg (133 KB, 800x1199)
Короче, я нашел, откуда придет апокалипсис для криптографии и всего Интернета:
https://www.satcompetition.org/2011/format-benchmarks2011.html
Сайт каждый год устраивает соревнования (в 2019 в июле) по решению SAT-задачи. Это задача нахождения набора, выполняющего формулу. Наборы даны в 3-CNF формате, как я понял.
SAT - это самая первая NP-полная задача, и самая универсальная. Потому что двоичная формула может описывать, что угодно, разложение числа или вычисление дискретного модуля, например.

TL;DR это такие олимпиадки по программированию для взрослых дядечек, которых не пустят на обычные олимпиадки

Может, кто-то из анонов захочет принять участие?
Anonymous No.644
IZ1tx2DT3Rc.jpg (183 KB, 864x1080)
>>450
По этой идее, кстати, выходит, что самые трудные инстансы в NP-полной задаче о сумме подмножеств — ровно те, которые получаются из задачи 3-CNF.

А именно это инстансы, в которых идут
x_0, x_1 : x_0, x_1 > \sum_j=2^n x_j
x_2, x_3 : x_2, x_3 > \sum_j=4^n x_j
x_4, x_5 : x_4, x_5 > \sum_j=6^n x_j
...
Ну вы поняли, такая горка, где идут два супервозрастающих по отношению к остальным элементам. Потом следуют еще два супервозрастающих к остатку элемента. И так, до конца.

Здесь "умный" комбинированный алгоритм (похожая техника описана кстати у Писинжера в "Fast algorithm for strongly correlated knapsack problems", 1998, только у него в качестве GA используется алгоритм поиска break item (особого элемента, нарушающего "баланс" и выводящего набираемую сумму за ограничение, задаваемое задачей)) неизбежно выродится в полный перебор всех возможных значений. Ну то есть выродится в перебор та часть алгоритма, которая динамическое программирование.

Я за почти 3 месяца не придумал ничего умнее, кроме как группировать некоторые "большие" элементы и рассматривать перебор нескольких "больших" элементов и жадный алгоритм на остатке. Затем спустится на уровень ниже, зафиксировав результат перебора "больших" элементов, и повторить перебор уровнем ниже (не забыв снова запустить жадный алгоритм на остатке). Получается приблизительный алгоритм с какой-то фантастической точностью, но все же приблизительный.

Хотелось бы иметь точный, пусть даже экспоненциальный алгоритм с 2^n/8 или 2^n/4 сложностью (с 2^n/2 не предлагать, такой вариант описан еще в фундаментальное работе Горовиц, Сахни, 1971. Хотелось бы эту оценку улучшить)
Anonymous No.764
photo_2019-06-2[...].jpg (48 KB, 720x915)
pic1.jpg (592 KB, 1366x649)
pic2.jpg (688 KB, 1366x656)
pic3.jpg (330 KB, 1366x331)
>>450
Написал подробное описание, сделал тесты для случайных инстансов. "Научная" статья уровня 2channel, лол.

Итог: мой накиданный алгоритм сосет у приближенных по времени, зато находит точное решение за более-менее приемлемое время (все время в миллисекундах). Впрочем это касается только случайно распределенных весов. Если брать инстансы, преобразованные из задачи 3-CNF, то алгоритм сосет и у брутфорса, точнее, вырождаясь в этот самый брутфорс (Там где у брутфорса больше 100 стоят нули, означает, что для случайного экземпляра перебор так и не заканчивался. Интересно, что для 64-элементного множества еще возможно найти сумму, если распределить веса случайно. Хотя в худшем случае это тоже должна быть недостижимая задача, ибо 2^64 вариантов на ПеКе не перебрать).

Описание алгоритма.
В задаче о сумме подмножеств дано множество (мультимножество) целых чисел, и число, называемое суммой подмножеств. Необходимо выяснить, содержит ли данное множество (мультимножество) подмножество, сумма элементов которого будет равна сумме подмножеств. Эффективного (полиномиального) алгоритма для задачи пока не было найдено. Если наложить ограничения, что множество (мультимножество) содержит только целые положительные числа, задача всё равно останется NP-полной (без полиномиального алгоритма).
Но мы можем рассмотреть два «крайних» («граничных») случая, для которых полиномиальный алгоритм существует, более того, всегда даёт точное значение. Мы рассматриваем только множества и мультимножества положительных целых чисел, отсортированных по убыванию, если не упоминается обратное.
Случай 1. «Снизу». Пусть элементы множества «максимально близко» идут друг к другу, то есть отстают друг друга на некоторый постоянный шаг d (d = 0, 1, 2, 3, …). Это хорошо известный случай арифметической прогрессии. Несмотря на то, что количество возможных подмножеств всегда экспоненциально (2^n для размера множества n), количество возможных сумм (пространство поиска) в этом случае полиномиально. Пространство поиска изменяется от s_1 до суммы всех элементов (s_1 + s_n) n / 2. Таким образом, размер пространства поиска всего лишь (1 + n) n / 2. Для такого крайнего случая динамическое программирование с хэш-таблицей (рекуррентный алгоритм, использующий хэш-таблицу вместо матрицы, ссылка на Пападимитриу) всегда даст полиномиальное время работы и полиномиальную память.
Случай 2. «Сверху». Пусть элементы множества «максимально далеко» расположены друг от друга, то есть отличаются в некоторое целое положительное число q раз (q = 1, 2, 3, …). Это хорошо известный случай геометрической прогрессии и пример супервозрастающей последовательности. Количество возможных сумм в этом случае экспоненциально, однако, нетрудно заметить, что обычный жадный алгоритм для такой последовательности всегда даст точное решение. Например, при задании следующего множества (…, 16, 8, 4, 2, 1) мы раскладываем число по степеням двойки именно с помощью жадного алгоритма. При переводе числа из десятичного основания в двоичное мы не задумываемся о корректности разложения, именно потому, что для супервозрастающей последовательности жадный алгоритм всегда будет точным.
Рассмотренные два случая являются достаточно общими. Естественным выводом напрашивается комбинированный «гибридный» алгоритм, сочетающий в себе жадный алгоритм (для случая «сверху») и динамическое программирование (для случая «снизу»): Hybrid = Greedy Algorithm + Dynamic Programming.
Проверим, является ли первый элемент «супервозрастающим» для остальных элементов множества. Для этого сравним величину первого элемента и сумму остальных элементов. Если величина первого элемента больше суммы оставшихся элементов, но при этом меньше искомой суммы подмножеств, включим первый элемент в подмножество. Если же величина первого элемента меньше суммы остальных элементов, применим рекурсивно динамическое программирование с хэш-таблицей для поиска K[v]. При вызове рекурсии проверяем каждый следующий элемент на «супервозрастание» с остатком множества.


Сравнение
Сравнение гибридного алгоритма и:
- жадного алгоритма
- жадного алгоритма Martello и Toth
- полного перебора
- аппроксимирующей схемы, построенной на алгоритме слияния списков

Реализация:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace hybrid
{
class Program
{
static int[] s;
static int v;
static Dictionary<int, int> K = new Dictionary<int, int>();

static void Init(string filename)
{
using (StreamReader sr = new StreamReader(filename))
{
string[] ss = sr.ReadLine()
.Split(new string[] { " ", "\t" },
StringSplitOptions.RemoveEmptyEntries);
int n = ss.Length - 1;
s = new int[n];

for (int i = 0; i < n; i++)
{
s[i] = int.Parse(ss[i]);
}
v = int.Parse(ss[ss.Length - 1]);
Array.Sort(s, (a, b) => -Math.Abs(a).CompareTo(Math.Abs(b)));
}
}

static int Hybrid(int[] x, int[] s, int v)
{
if (K.ContainsKey(v))
return K[v];
if (s.Length == 0)
return 0;
int[] sNew = new int[s.Length - 1];
Array.Copy(s, 1, sNew, 0, s.Length - 1);
int[] xNew = new int[s.Length - 1];

if (s[0] > v)
{
x[0] = 0;
K[v] = Hybrid(xNew, sNew, v);
for (int j = 1; j < x.Length; j++)
x[j] = xNew[j - 1];
return K[v];
}

int tempSum = 0;
for (int j = 1; j < s.Length; j++)
tempSum += s[j];
if (s[0] > tempSum)
{
x[0] = s[0];
K[v] = s[0] + Hybrid(xNew, sNew, v - s[0]);
for (int j = 1; j < x.Length; j++)
x[j] = xNew[j - 1];
return K[v];
}

int eps = int.MaxValue;
for (int i = 0; i < s.Length; i++)
{
for (int j = 0; j < i; j++)
sNew[j] = s[j];
for (int j = i + 1; j < s.Length; j++)
sNew[j - 1] = s[j];
if (s[i] <= v)
{
int t = Hybrid(xNew, sNew, v - s[i]);
if (v - s[i] - t < eps)
{
for (int j = 0; j < i; j++)
x[j] = xNew[j];
for (int j = i + 1; j < x.Length; j++)
x[j] = xNew[j - 1];
x[i] = s[i];
K[v] = s[i] + t;
if (s[i] + t == v)
return s[i] + t;
eps = v - s[i] - t;
}
}
}
return K[v];
}

static void PrintTime(double timeDistanceMs = 0)
{
File.AppendAllLines("outputTime.txt", new string[] { timeDistanceMs.ToString() });
}

static void Main(string[] args)
{
Console.WriteLine("Filename: ");
string filename = Console.ReadLine();
Init(filename);
int[] x = new int[s.Length];
var timeBefore = DateTime.Now;
Hybrid(x, s, v);
var timeAfter = DateTime.Now;
PrintTime((timeAfter - timeBefore).TotalMilliseconds);
Console.ReadKey();
}
}
}
Anonymous No.765
>>764
Вкратце, что ты сделал?
Anonymous No.767
x8x-57x5sqM.jpg (171 KB, 729x959)
>>765
Операции проводятся над положительными, отсортированными по убыванию числами (это так, например: 10, 8, 7, 6, 6, 4, 1)
Взял алгоритм из Пападимитриу рекурсивного динамического программирования (с хэш-таблицей). Добавил два условия:
1) Если элемент больше набираемой суммы, просто отбрасываем его (логично).
2) Если элемент больше суммы всех остальных элементов, без всяких добавляем его в ответ, уменьшаем набираемую сумму на величину этого элемента (не так очевидно, но тоже очевидно, если подумать).
Anonymous No.865
>>334 (OP)
Доверилсь, ну так доверились и что. Зачем шифрование в некоторых сервисах? Мне скрывать нечего, когда я в ВК пишу.
Anonymous No.869
Сап, двачанский
Не спится, даже морфий не помогаетъ.
Вот размышляю я и думаю, а что, если мы все обосралiсь в 1917? Обратившись, когда доверились криптографии Вернама. Потом доверились механическим шифровальным машинам.
Ведь криптография по ХОР базируется на предположении, что одни одноразовый блокнот "труднее" других. Что его нельзя расшифровать.
Да, обратное не доказано.
Да, большинство мировых учёных думает (вдумайся, анон, просто думает), что одноразовый блокнот криптостоек.



...


Похуй.
Anonymous No.875
>>342
>Freenet уважаю, он намного более приватен, чем Tor и i2p даже
На чём основывается приватность сети? Чем одна сеть приватнее другой?
Anonymous No.879
>>875
Тред не читал и хз почему так считает оп, но сходу могу назвать несколько пунктов:
1) "Мусорный" трафик из коробки - в торе тебя теоретически гораздо проще сданонить просто сопоставив время подключения и хоть и примерное распределение трафика по времени. Для гебни это просто. В ш2з так вообще некоторое число других участников знает когда ты в сеть выходишь, хотя там вроде, я не уверен, тоже есть левый трафик
2) Plausible deniability - если к тебе пришли мусора и обнаружили на жд какое-нибудь цп или оскорбление пыни в хранилище фринета, ты теоретически можешь заявить что твой комп просто перенаправлял трафик и закешировал (потому что так работает фринет). Другое дело что с Kafkaesque в цивилизованных странах и пидорахии это вряд ли прокатит.
3) Сайтам не нужен сервер. Т.е. ты загрузил свою домашнуюю страничку васяна и можешь вообще фринет удалять. Нет сервера - нет дыр в сервере. Другое дело что динамические сайты невозможны, и чуть менее чем все форумы засраны спамом, но это уже другой вопрос.

Изобилие ЦП вообще показатель секурности имхо.
И это в фринете ещё нет тунелей, вот когда если будут то это вообще монстр будет.
Anonymous No.884
>>879
Проблемы с обновлением страницы. Есть ли фринет с обновлением страниц?
Anonymous No.900
>>884
Эм? Там есть USK.

[Назад] [Обновить тред] [Вверх] [Каталог] [ Автообновление ]
25 / 13 / 17

[Ответить в тред] Ответить в тред

Ответ в тред No.334
15000
Файлы. Макс объем: 20 MB, макс кол-во файлов: 4

Ответ в тред No.334X
15000
Файлы. Макс объем: 20 MB, макс кол-во файлов: 4
Кликни/Брось файл/ctrl-v
НастройкиX
X
Избранное
Топ тредов