  In this work we consider the following problem: in a Multi-Prover
environment, how close can we get to prove the validity of an NP statement in
Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the
3-COLorability problem that use two (local) provers or three (entangled)
provers and only require them to reply two trits each. This greatly improves
the ability to prove Zero-Knowledge statements on very short distances with
very minimal equipment.
