>>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 менять нельзя.

Это, если что, просто размышления, не стоит относиться серьезно.

>>351
Да, все ключи придется раздавать в оффлайне. Если банкам - норм., то как быть с "Вконтакте", "Фейсбуками" и т.д.?
Вебу 2.0 нормис придет каюк. Хочешь иметь свою страницу в Интернет - придется и хостинг держать на своем железе. И ограничить пользователей от посыла какой-либо информации. Только статика, только хардкор!

С позволения, цитата из Пападимитриу "Алгоритмы":
> Существуют ли задачи поиска, которые не могут быть решены за полиномиальное время? Другими словами, верно ли, что 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) сможет избежать экспоненциального перебора для любого множества.

Это, конечно, никакое не доказательство, просто контр-аргумент, приведенный к аргументу Пападимитриу. На таком же, нестрогом уровне.

>>334 (OP)
Как обстоят дела с квантовыми компьютерами?

>>460
Для них есть два отдельных раздела:
1) Постквантовая криптография — криптография на обычных компьютерах, после того, как алгоритм Шора реализуют на уровне круче чем 15 = 3 * 5
2) Квантовая криптография — криптография с использованием квантовых эффектов.

Однако, если P = NP, то и алгоритмы постквантовой криптографии становятся ненужными и взламываемыми. Если же реализовать квантовый компьютер, то решение NP-полных задач на нем будет занимать в асимптоте столько же время, сколько и на обычном. Короче, созданный рабочий квантовый компьютер приведёт к пересмотру используемых шифров (с RSA и эллипитических кривых на Hidden Field Equations, например). Решение P = NP, если оно существует, уничтожит ассиметричную криптографию вообще.

Короче, я нашел, откуда придет апокалипсис для криптографии и всего Интернета:
https://www.satcompetition.org/2011/format-benchmarks2011.html
Сайт каждый год устраивает соревнования (в 2019 в июле) по решению SAT-задачи. Это задача нахождения набора, выполняющего формулу. Наборы даны в 3-CNF формате, как я понял.
SAT - это самая первая NP-полная задача, и самая универсальная. Потому что двоичная формула может описывать, что угодно, разложение числа или вычисление дискретного модуля, например.

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

Может, кто-то из анонов захочет принять участие?

>>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. Хотелось бы эту оценку улучшить)

>>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();
}
}
}

>>765
Операции проводятся над положительными, отсортированными по убыванию числами (это так, например: 10, 8, 7, 6, 6, 4, 1)
Взял алгоритм из Пападимитриу рекурсивного динамического программирования (с хэш-таблицей). Добавил два условия:
1) Если элемент больше набираемой суммы, просто отбрасываем его (логично).
2) Если элемент больше суммы всех остальных элементов, без всяких добавляем его в ответ, уменьшаем набираемую сумму на величину этого элемента (не так очевидно, но тоже очевидно, если подумать).

>>470
Чтобы принять участие надо хоть немного понимать о чём это.
Скидывай туториал по вкату в SAT-солвинг. Звучит интересно.

>>2761
Их равенство и означает возможность брутфорса.

>>334 (OP)
>А что если все мы допустили одну большую ошибку

Кто мы-то?

Начальник! Начальник! Этот пидорас обосрался!

Spectre и meltdown делают твоё фыфрование бесполезным даже не на программном уровне, на железном! И это только широко известные лазейки. Смартфоны и прочие фигни вообще одно сплошное решето. С сумасшедшим поселили! Начальник!

>>2765
Там же типичная side-channel атака. Нужно считать такты процессора и собирать статистику по каждому байту по тактам. Несколько килобайт текста, если иметь доступ к железу, реально прочитать за несколько минут (тред про способы шифрования в сети, как я понимаю, про защиту от перехвата того, что на проводах и в радиоволнах, а не того, что на конечной ПеКе). Ну и как бы вся фишка защиты в рандомизации страниц и адресного пространства оперативной памяти, чтобы искомые несколько килобайт нельзя было получить, просто ткнув пальцем

>>3211
Спутники летают на формулах СТО, а не ОТО. И даже не спутники летают, а работают GPS и Глонасс, каждый раз находя себя на карте смартфона, вы подтверждаете корректность преобразований Лоренца в СТО. То что верна СТО, не просто предположения - уже даже у самых упертых фриков нет сомнения, достань GPS, не знаю, попробуй трилатерацию мощного радиопередатчика сделать по любительским SDR-приемникам и определить его местоположение. А вот с ОТО сложнее, мне, например, нравятся выводы РТГ Логунова о том, что сингулярностей в природе не существует, а те черные дыры, которые находят, на самом деле не черные дыры, а коллапсары (впрочем для мимопролетающего алиена будет похуй, какая там первая космическая, чтобы выйти из поля притяжения и лететь дальше - больше световой, световая или всего 0,99c). Раз нет сингулярностей - нет и парадокса "исчезновения информации в черной дыре". Но РТГ считается "альтернативной физикой", хоть и не совсем фриканутой