Comment by marshray
9 hours ago
> The subexponential solution does carry over to any (?) problems that have can be reduced to 3SAT in a linear number of variables. They list: Counting independent sets, Counting proper q-colorings, Counting perfect matchings.
Wouldn't that also include functions that can be evaluated in hardware using a fixed number of gates? E.g., symmetric cryptography?
A circuit with a fixed number of (binary logical) gates can be solved in constant time, as it will have a fixed number of input bits, so brute force will have a fixed number of input options to consider. This does apply to cryptographic algorithms with a fixed key size, like the ones used in practice, as well. The whole point of computational complexity is to look at the scaling behavior when you increase the inputs/key size/size of the circuit.
From my reading no. Because brute forcing anything symmetrical is already O(n). What protects us is the assumption that there is not enough energy in the observable universe to brute force 2^256 key.