There are 2 much better criticism they could have made:
1. The proof is conditional on the unproven hypothesis that 3-SAT requires 2^n time.
2. There could be an exact algorithm which uses randomness and has less than n^2 expected runtime. After all, it's still unknown whether ZPP=EXP afaik (although it almost certainly does not).
1. The proof is conditional on the unproven hypothesis that 3-SAT requires 2^n time.
2. There could be an exact algorithm which uses randomness and has less than n^2 expected runtime. After all, it's still unknown whether ZPP=EXP afaik (although it almost certainly does not).