Comments 2
А почему статью заминусили?
Видимо потому что слишком много наукообразного словооблудия с врезками "да я поверить не мог, но вот так удача" без нормального экскурса про собственно, а что они сделали. Нейро в этом смысле лучше справился
tldr
История доказательств
• Математики используют базовые предположения для доказательства истинности утверждений.
• В 1980-х и 1990-х годах учёные-информатики разработали новые подходы к доказательствам.
• Доказательства с нулевым знанием и вероятностно проверяемые доказательства стали важными изобретениями.
Доказательства с нулевым знанием
• Доказательства с нулевым знанием убеждают в истинности утверждения, не раскрывая причин.
• Они используют интерактивность и случайность для проверки решений.
• Пример: доказательство раскраски карты с помощью интерактивного процесса.
Вероятностно проверяемые доказательства
• Вероятностно проверяемые доказательства (PCP) могут быть проверены с помощью небольших фрагментов.
• Они умножают и распространяют ошибки, делая их заметными.
• PCP ускоряют проверку для задач NP.
Объединение доказательств
• В 2020 году Гур и другие исследователи объединили доказательства с нулевым знанием и PCP для важного класса задач.
• Это важный результат, решающий старую проблему.
Будущие исследования
• Исследователи продолжают работать над улучшением доказательств, чтобы получить лучшее из обоих миров.
Проблемы с вероятностной проверяемостью и нулевым знанием
• Неинтерактивная природа PCP создаёт проблемы с нулевым знанием.
• Обычные доказательства с нулевым знанием требуют интерактивности для ограничения доступа проверяющего.
• Неинтерактивные доказательства могут быть использованы для кражи секретов доказывающего.
Попытки создания PCP с нулевым знанием
• В 1997 году исследователи создали PCP с нулевым знанием для NEXP, но с добавлением интерактивности.
• Результат не соответствовал идеалу нулевого знания, но был полезен для криптографии.
Современные достижения
• В 2017 году Николас Спунер предложил идею идеального PCP с нулевым знанием.
• Гур не был убеждён, но изменил мнение после демонстрации трюка Спунером.
• Спунер, Гур и О'Коннор построили идеальный PCP с нулевым знанием для задач подсчёта.
Будущие планы
• Исследователи намерены расширить метод на все проблемы NEXP.
• Новый метод может привести к доказательству аналога теоремы PCP с нулевым знанием.
• Новые методы могут найти применение в других отраслях информатики.
Специалисты по информатике объединили два «красивых» метода доказательства