I think it’s worth distinguishing between “smallest” and “fastest” circuits.
A note on smallest.
1) Consider a travelling salesman problem and a small program that brute-forces the solution to it. If the “deamon” wants to make a travelling salesman visit a particular city first, then they would simply order the solution space to consider it first. This has no guarantee of working, but the deamon would get what it wants some of the time. More generally, if there is a class of solutions we are indifferent to, but daemons have a preference order over, then nearly all deterministic algorithms could be seen as deamons. That said, this situation may be “acceptable” and it’s worth re-defining the problem to exactly understand what is acceptable and what isn’t.
A note on fastest
2) Consider a prime-generation problem, where we want some large primes between 10^100 and 10^200. A simple algorithm that hardcodes a set of primes and returns them is “fast”. This isn’t the smallest, since it has to store the primes. In a less silly example, a general prime-returning algorithm could only look for primes of particular types, such as Mersenne primes. The general intuition is that optimizations that make algorithms “faster” could come at a cost of forcing a particular probability distribution on the solution.
I think it’s worth distinguishing between “smallest” and “fastest” circuits.
A note on smallest.
1) Consider a travelling salesman problem and a small program that brute-forces the solution to it. If the “deamon” wants to make a travelling salesman visit a particular city first, then they would simply order the solution space to consider it first. This has no guarantee of working, but the deamon would get what it wants some of the time. More generally, if there is a class of solutions we are indifferent to, but daemons have a preference order over, then nearly all deterministic algorithms could be seen as deamons. That said, this situation may be “acceptable” and it’s worth re-defining the problem to exactly understand what is acceptable and what isn’t.
A note on fastest
2) Consider a prime-generation problem, where we want some large primes between 10^100 and 10^200. A simple algorithm that hardcodes a set of primes and returns them is “fast”. This isn’t the smallest, since it has to store the primes. In a less silly example, a general prime-returning algorithm could only look for primes of particular types, such as Mersenne primes. The general intuition is that optimizations that make algorithms “faster” could come at a cost of forcing a particular probability distribution on the solution.