Are you allowed to change the specifications of a problem when doing reductions?
-
05-11-2019 - |
题
I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. However, the input of problem A does not give me enough information to be able carry out all of these demands that problem B require.
My reduction will look something like this:
**A**(G(V, E), K) =
a = V
b = E
P = **B**(a, b, K)
if(P)
return true
My question is if it is okay to ignore some of these demands and simply change the B problem to a simpler one which then would allow me to find a reduction which satisfies both problems?
I'm sorry for being so vague, it is a homework problem and I would like to not publish the details.
没有正确的解决方案
不隶属于 cs.stackexchange