There’s a natural partial mapping in my mind, but a rigorous mapping is beyond me. Check out this. Apparently it can be shown that FNP is strictly harder than NP, under certain conditions. I didn’t understand the condition, and whether it was reasonable or not.
Regardless of all this complexity jazz, which has definitely exceeded my grasp, my random dictionary example still demonstrates that certain problems can be solved exponentially faster with postselection than without, even if it doesn’t prove that FNP > NP.
ETA: Coming from a numerics background, decision problems seem like exotic beasts. I’d prefer to settle the power of quantum voodoo on function problems first =P
There’s a natural partial mapping in my mind, but a rigorous mapping is beyond me. Check out this. Apparently it can be shown that FNP is strictly harder than NP, under certain conditions. I didn’t understand the condition, and whether it was reasonable or not.
Regardless of all this complexity jazz, which has definitely exceeded my grasp, my random dictionary example still demonstrates that certain problems can be solved exponentially faster with postselection than without, even if it doesn’t prove that FNP > NP.
ETA: Coming from a numerics background, decision problems seem like exotic beasts. I’d prefer to settle the power of quantum voodoo on function problems first =P