## 3 Problem Formulation  
Let \(\mathcal{P}\) denote the space of computational problems, where each problem \(p\in\mathcal{P}\) is defined by \(p=(\mathcal{I}_{p},\mathcal{Y}_{p},\mathcal{C}_{p})\). Here, \(\mathcal{I}_{p}\) and \(\mathcal{Y}_{p}\) represent input and output spaces, respectively, and \(\mathcal{C}_{p}:\mathcal{I}_{p}\times\mathcal{Y}_{p}\rightarrow\mathbb{R}\) is the cost function evaluating solution quality. A heuristic \(h\) for problem \(p\) is a function \(h:\mathcal{I}_{p}\rightarrow\mathcal{Y}_{p}\). Automatic heuristic design aims to generate \(h\) from example pairs \(E_{p}=\{(i_{k},y_{k})\}_{k=1}^{p}\) with \(i_{k}\in\mathcal{I}_{p}\) and \(y_{k}\in\mathcal{Y}_{p}\).  
The space of possible heuristics \(\mathcal{H}\) is defined over atomic operators \(\mathcal{A}\) and composition rules \(\mathcal{R}\). A heuristic \(h\in\mathcal{H}\) can be expressed as a composition of primitives:  
\[h=r_{m}(a_{m_{1}},r_{m-1}(a_{m_{1}-1},\ldots,r_{1}(a_{1},i)\ldots))\]  
where \(a_{j}\in\mathcal{A}\) and \(r_{k}\in\mathcal{R}\). The goal is to find \(h^{*}=\arg\min_{h\in\mathcal{H}}\mathbb{E}_{i\in\mathcal{I}_{p}}[\mathcal{C}_ {p}(i,h(i))]\), approximated via empirical risk minimization:  
\[h^{*}\approx\arg\min_{h\in\mathcal{H}}\frac{1}{|E_{p}|}\sum_{(i,\omega)\in E_{ p}}\mathcal{C}_{p}(i,h(i))\]  
For parameterized heuristics \(h_{\theta}\) with \(\theta\in\Theta\), the optimal parameters \(\theta^{*}\) are to minimize:  
\[\theta^{*}=\arg\min_{\theta\in\Theta}\mathcal{L}(h_{\theta},E_{p})+\lambda \Omega(\theta)\]  
where \(\mathcal{L}\) measures discrepancy (such as cosine distance function), \(\Omega\) regularizes complexity (such as \(L_{1}\) norm), and \(\lambda\) balances the trade-off.  
The design process is modeled as a sequential decision-making problem with states \(s_{t}\), actions \(a_{t}\), and rewards \(r_{t}\). The optimal policy \(\pi^{*}\) maximizes cumulative reward:  
\[\pi^{*}=\arg\max_{\pi}\mathbb{E}\left[\sum_{t=0}^{T}\gamma^{t}r_{t}\mid\pi\right]\]  
where \(\gamma\in[0,1)\) is the discount factor. Optimization is typically performed using reinforcement learning, genetic programming, or gradient-based methods.  
Algorithm Discovery as a Special Case  
Algorithm discovery can be viewed as a constrained instance of automatic heuristic design, where the goal is to generate provably correct algorithms \(A\) for problem \(p\). This is formalized by restricting the heuristic space \(\mathcal{H}\) to a subset \(\mathcal{H}_{\text{alg}}\subset\mathcal{H}\) that satisfies correctness constraints \(\mathcal{C}_{\text{correct}}(A,p)\):  
\[\mathcal{H}_{\text{alg}}=\{A\in\mathcal{H}\mid\forall i\in\mathcal{I}_{p},\ \mathcal{C}_{p}(i,A(i))\leq\mathcal{C}_{p}^{*}(i)+\epsilon\}\]  
where \(\mathcal{C}_{p}^{*}(i)\) is the optimal cost and \(\epsilon\) bounds error. Algorithm discovery seeks:  
\[A^{*}=\arg\min_{A\in\mathcal{H}_{\text{alg}}}\sup_{i\in\mathcal{I}_{p}} \mathcal{C}_{p}(i,A(i))\]  
subject to structural constraints (e.g., finite-time termination) and verifiable correctness. This is often achieved by augmenting the objective with a penalty term:  
\[A^{*}=\arg\min_{A\in\mathcal{H}}\mathbb{E}_{i\in\mathcal{I}_{p}}[\mathcal{C}_{ p}(i,A(i))]+\lambda\cdot\mathcal{I}(\mathcal{C}_{\text{correct}}(A,p))\]  
where \(\mathcal{I}\) is an indicator function and \(\lambda\rightarrow\infty\) enforces correctness.