#Dayoon Kim, 2024-4-21, HW25
Help:=proc(): print(` VerifyOpt1(n,G,B1,B2), ZKP(n,G,pi,K) `):
print(`  `): end:


#HW24-2.

#VerifyOpt1(n,G,B1,B2): inputs a positive integer n, a graph (set of edges) G, and tables B1 (of size n) and B2 (of size binomial(n,2)) 
#and outputs true if it is a faithful relabling of the graph G, otherwise false.
VerifyOpt1:=proc(n,G,B1,B2) local i,j,sig,G_relabel:
sig:=B1:
G_relabel:={}:

for i from 1 to n do
 for j from i+1 to n do
   if B2[{sig[i],sig[j]}]=1 then
     G_relabel:=G_relabel union {{i,j}}:
   fi:
 od:
od:

if G_relabel=G then
 true:
else
 false:
fi:
end:


#HW24-3.
#ZKP(n,G,pi,K): performs K rounds of the ZKP1(n,G,pi,Opt) procedure, picking Option 1 or Option 2 each with probability 1/2
# and returning true if and only if ZKP1(n,G,pi,Opt) always returns true.
ZKP:=proc(n,G,pi,K) local i,Opt,result:
for i from 1 to K do
 Opt:=rand(1..2)():
 result:=ZKP1(n,G,pi,Opt):
 if result=false then
  return false:
 fi:
od:
return true:
end: