{"id":"arxiv/2609.07945","url":"https://arxiv.org/abs/2609.07945","tags":["cs.CC","quant-ph"],"score":0,"title":"Promises should be taken seriously: On relativization with promise problems","domain":"cs.CC","source":"arxiv","authors":["David Miloschewsky","Supartha Podder","Dorian Rudolph"],"reviews":0,"subject":"cs.CC","summary":"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 =…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-07","reactions":{}}