SNARKs use decision problems, which are languages (subset of strings), and decides whether a given string in the WHOLE set of strings of finite length is a word in the language or not.

IF x in R then x is a word in associated language LR

The relation is itself a language that represents the GRAMMAR of the language.

Definitions

Statement S

• claim that language L contains a word x, a statement claims that there exists some x in L

Proof

• for a statement S, its given by some string P in set of all strings of finite length, and a proof is verified by checking if R(P) = true.

Instance

• a proof P is an instance of the statement if R(P) = true

Decision Function

• a function that decides whether a string is in the language or not.

Decision relation

• a language R (aka subset of all strings of finite length) that decides if its in some language L such that: if a string is in R, then the string is in L, if a string is not in R, then its not in L

Exercise 96

$$ R_{Exercise1} : (F_{13})^* -> \{true, false\}; \{x_1,...x_n\} -> \{true: n=1 and(5x+4=28+2x), false: else\} $$