Promises should be taken seriously: On relativization with promise problems

David Miloschewsky, Supartha Podder, Dorian Rudolph

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…