Promises should be taken seriously: On relativization with promise problems
Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of the promise being unconstrained. We study two semantics for such access. Under robust queries, a machine must correctly answer regardless of the completion of the problem,, while loose access requires that the internal choices of a machine do not change based on off-promise queries. Our first result separates the language and promise settings. Namely, we construct an oracle $O$ such that $\mathsf{P}^O =…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.07945
curl -X POST /api/v1/records/arxiv/2609.07945/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.07945/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'