4 ms·
If you're looking for a proof that the Benesh network can implement any permutation (of size 2^n): https://eng.libretexts.org/Bookshelves/Computer_Science/Prog
by H8crilA 3y ago
If you're looking for a proof that the Benesh network can implement any permutation (of size 2^n):
https://eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Mathematics_for_Computer_Science_(Lehman_Leighton_and_Meyer)/02%3A_Structures/10%3A_Communication_Networks/10.09%3A_Benes_Network https://eng.libretexts.org/Bookshelves/Computer_Science/Prog...
The proof is not super complicated, but it for sure isn't trivial.
- TontonNestor 3y agoThe author seems to think it's a simple exercise, but I agree with you, the proof that you linked, which uses graph coloring, and those in the Beneš or Waksman articles, which use Hall's theorem, are per se easy to understand, but rather hard to come up with.