#OK to post homework
#GLORIA LIU, Apr 20 2024, Assignment 25

read `C27.txt`:

#=====================================#
#1. Continue to work on your project due May 1, 11:00pm

#=====================================#
#2. Write a procedure
#MetaZKP3(n,E,C,K) where the verifier asks the prover K questions and randomly picks the option (each with prob. 1/2) 
#and if it is true all the times returns true, if it is false even one time, it returns false.
#Once you have it, and experiment with several large graphs and asociated cloring, gotten from RGC3(n) and convince 
#yourself that the graph is genuine, using K=20.
#Now change the coloring randomly (so it is probably no longer proper) and see whether MetaZKP3(n,E,C,20) is still true.

MetaZKP3:=proc(n,E,C,K) local i,ra:
 ra:=rand(1..2)():
 for i from 1 to K do
  if ZKP3(n,E,C,ra())=false then
   RETURN(false):
  fi:
 od:
true:
end:

result:={}:
for i from 1 to 5 do
 n:=rand(50..100)():
 RGC:=RGC3(n):
 result:=result union {MetaZKP3(RGC,20)}:
od:

result;
#All true

result:={}:
#improper coloring
for i from 1 to 5 do
 n:=rand(50..100)():
 RGC:=RGC3(n):
 E:=RGC[2]:
 C:=[seq(rand(1..3)(), i=1..n)]:
 result:=result union {MetaZKP3(n,E,C,20)}:
od:

result;
#True and false

#=====================================#
#3. Read and understand the alternative, hopefully simpler approach (pointed out by George Spahn) and implement it.
#Skipped