trixthethird

4 ms·

1. 1.▲
   by trixthethird 1y ago

   I think you are right. I just read this article linked in the OP: https://www.quantamagazine.org/an-easy-sounding-problem-yiel...
2. 2.▲
   by trixthethird 1y ago

   This applies to any computable problem though, no? At minimum the verifier has to read the witness. If we ignore PCPs and such. The point here is that the witness grows very fast in terms of vector dimensionality and/or move set size.
3. 3.▲
   by trixthethird 1y ago

   I think they proved it grows with Ackermann function.
4. 4.▲
   by trixthethird 1y ago

   Linear time in the length of the sequence, yes. But is the sequence length linear in dimension size, or number of moves given? Thats what is interesting.
5. 5.▲
   by trixthethird 1y ago

   How does it compare to org-roam? Seems like colab and web-serving is the main diff?