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.

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top