Bellman's Forest Problem and Computability
The goal of this paper is to refine methods in computable analysis and to employ them in the study of solutions of an optimization problem posed by Bellman. This problem asks how to find optimal (shortest) paths which do not fit into given plane figures. We show that each instance of Bellman's problem has an arbitrarily small uniformly computable perturbation for which the minimal length of path is computable, and thus the class of optimal paths is a $Π_1^0$ class, and there are uniformly computable paths which escape with arbitrarily small length greater than the minimum possible.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.31352
curl -X POST /api/v1/records/arxiv/2609.31352/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.31352/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'