alt Hacker NewsI think that it'd be funny if the polynomial time SAT solver was just "send your SAT instance to Astra and have it try to solve it for a few hours."
I think that it'd be funny if the polynomial time SAT solver was just "send your SAT instance to Astra and have it try to solve it for a few hours."
I wonder if there are proofs regarding what neural networks like the transformer can solve. Because fundamentally, Astra is just a bunch of matrix multiplications and a few well defined non-linear functions.
Anyways, most of the times, SAT can be solved quickly, but not always, so getting the answer from Astra in polynomial time doesn't prove much unless you can also prove that it always does, no matter the input.