Регистрация Войти
Рейтинг:0
avatar Crypto

Доказательство вывода универсальной функции

флаг ma
Matteo Monti

Существует ли какая-либо общая конструкция для доказательства правильности вывода функции? Другими словами, есть ли общий способ представить свидетеля для заявления? $у = е(х)$?

Более формально пусть $f: X \стрелка вправо Y$ быть общей функцией. Данный $f$, существует ли какой-либо общий способ создания функции генерации свидетелей $p: X \стрелка вправо W$ и предложение $V(х, у, ш)$ такой, что для всех $х$, Только $V(x,f(x),p(x))$ верно, и проверка $V(х, у, ш)$ быстрее, чем вычисления $ф(х)$?

36
0 + 0
Maarten Bodewes avatar
флаг in
Maarten Bodewes
Разве односторонние функции не опровергают это?
0
Ответить
poncho avatar
флаг my
poncho
Одной из функций, которая может быть контрпримером, является функция $f(x)=0$ (для любого $x$); да, для этого $f$ легко построить предложение; Я не знаю, сможете ли вы построить систему, которая работает **быстрее**, чем вычисление $f$...
2
Ответить
флаг ma
Matteo Monti
@poncho, я думаю, это довольно справедливое замечание.
0
Ответить
Wilson avatar
флаг se
Wilson
Чтобы уточнить, если я читаю это правильно. Вам интересно, существует ли краткое доказательство и эффективный алгоритм проверки (за время, меньшее, чем оценка функции), чтобы проверить, что для общедоступных f, x и y y = f (x)?
0
Ответить
флаг ma
Matteo Monti
@Уилсон точно! Я знаю, что он существует для некоторых функций (например, односторонние функции могут использовать свои выходные данные в качестве свидетелей), поэтому мне интересно, существует ли какой-то более общий механизм!
0
Ответить
Wilson avatar
флаг se
Wilson
Рассмотрим общую функцию f, представленную ансамблем арифметических схем. Разве эта проблема не решается предварительной обработкой SNARK? Временная сложность верификатора является полилогарифмической по сложности схемы. Существует также линия литературы, называемая проверяемыми вычислениями, которая, возможно, также является тем, что вы ищете.
0
Ответить
Wilson avatar
флаг se
Wilson
Давайте рассмотрим контрпример с пончо в контексте. $f(x)=0$ — функция, вычислимая за постоянное время. Таким образом, постоянные факторы в алгоритме проверки будут перевешивать логарифмическую сложность, но для нетривиальных функций этот метод будет лучше, чем вычисление функции.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.