Sudoku is a great example: everyone knows it, many consider a fun, some are using as a toy case to explain/introduce their ideas.
It was a boost/inspiration for me to watch Bitcoin workshop FC16 demo, read the code and detailed explanation on Bitcoincore, watch QED video presentation. Thank you! It also raised a case of testing “complex” statements with characteristic polynomials.
At a glance, “is a valid solution” is set equality test, repeated for all rows, columns and blocks. I was looking into operations with sets, identifying “Set reconciliation…” approach/paper of Ari Trachtenberg as maybe the best path forward. It worked best for me for graphs actually, not exactly sets. Well, maybe until Sudoku.
An efficient set equality operation may look like this:
we assign a prime number for each set element, and compare products for two sets.
It happen we better assign relatively prime polynomials instead, and test polynomial equivalence by evaluating both at a random point; Schwartz-Zippel lemma gives upper bound for soundness error (probability to accept non-equal sets).
Documented at “Sudoku solvability proof”.
Well, somewhat incomplete yet: circuit and proving/verifying public keys generation probably done, giving complexity estimate.
SNARKs was my direction proposal, at least until resigning from SRK this April.
It is my point to consider characteristic polynomials as an “intermediate language” for statements about sets and graphs.
Thanx for reading