Y
HN Search
Hacker News Search
new
|
comments
|
top
|
jobs
trixthethird
searching PlanetScale…
1.
▲
2.
▲
3.
▲
4.
▲
5.
▲
6.
▲
2 ms
·
1.
▲
by
trixthethird
2y 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.
▲
by
trixthethird
2y 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.
▲
by
trixthethird
2y ago
I think they proved it grows with Ackermann function.
4.
▲
by
trixthethird
2y 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.
▲
by
trixthethird
2y ago
How does it compare to org-roam? Seems like colab and web-serving is the main diff?