Combinatorial explosion is the rapid growth of possible solutions when many choices or components can be combined. In program synthesis, expanding the specification or primitive vocabulary makes the search space grow far faster than ordinary exponential growth. section 19.4.5
Searching for a program
A traditional program-synthesis system may try possible programs until one matches a specification. This approach works for short programs, but quickly becomes impractical as programs become more complex. Human-like intuition or learned guidance can reduce the options that search must consider. section 19.4.5
The practical consequences are:
- Larger specifications create more candidate programs to evaluate. section 19.4.5
- A larger vocabulary of primitives expands the search space further. section 19.4.5
- Deep learning can guide search toward promising regions instead of examining every possibility. section 19.4.5
Figure 19.15 A learned program relying on both geometric primitives (pattern recognition, intuition) and algorithmic primitives (reasoning, search, memory)
Shows how learned programs can combine geometric primitives for pattern recognition with algorithmic primitives for reasoning, search, and memory. section 19.4.5
