#OK to post homework
#Joseph Koutsoutis, 04-21-2024, Assignment 25

read `C25.txt`:

#1 done

#2 


VerifyOpt1 := proc(n,G,B1,B2) local i,j:
 for i from 1 to n do:
  for j from i+1 to n do:
   if ({i,j} in G and B2[{B1[i], B1[j]}] = 0) or ((not ({i,j} in G)) and B2[{B1[i], B1[j]}] = 1) then:
    return(false):
   fi: 
  od:
 od:
 true:
end:



ZKP1:=proc(n,G,pi,Opt) local B1,B2,i,j,sig:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[i]:
od:

for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},G) then
     B2[{sig[i],sig[j]}]:=1:
   else
    B2[{sig[i],sig[j]}]:=0:
   fi:
od:
od:

if Opt=1 then
 VerifyOpt1(n,G,op(B1),op(B2)):
else
 evalb({1} = {seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}):
fi:
end:



#3


ZKP := proc(n,G,pi,K) local i,Opt:
 for i from 1 to K do:
  if LD(1/2) then:
   Opt := 1:
  else:
   Opt := 2:
  fi:
  if not ZKP1(n,G,pi,Opt) then return(false): fi:
 od:
 true:
end:


#4 I didn't attempt this challenge.