Remix.run Logo
▲ marshray 7 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?

▲pcbouman 3 hours ago | parent [-]

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.