New answers tagged interactive-proofs
2
votes
Accepted
Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)
The $NP$-problem here is not the problem of finding y,z,n, but rather the following problem:
"Given a mathematical statement $A$ that can be encoded in $n$ bits, does there exist a proof of $A$ ...
Top 50 recent answers are included
Related Tags
interactive-proofs × 61cc.complexity-theory × 32
complexity-classes × 12
quantum-computing × 11
zero-knowledge × 6
quantum-information × 4
pcp × 4
reference-request × 3
cr.crypto-security × 3
gt.game-theory × 3
nt.number-theory × 3
pspace × 3
ds.algorithms × 2
soft-question × 2
time-complexity × 2
big-picture × 2
space-bounded × 2
coq × 2
lg.learning × 1
np-complete × 1
communication-complexity × 1
coding-theory × 1
graph-colouring × 1
np × 1
derandomization × 1