由网友(岁梦半尺见)分享简介：是否有可能投任何子图同构的问题，因为一个子集和问题，因此，有可能利用现有的动态编程技术用于解决子集和问题的解决问题的SGI？Is it possible to cast any subgraph isomorphism problem as a subset sum problem so that it is pos...

是否有可能投任何子图同构的问题，因为一个子集和问题，因此，有可能利用现有的动态编程技术用于解决子集和问题的解决问题的SGI？

Is it possible to cast any subgraph isomorphism problem as a subset sum problem so that it is possible to use dynamic programming techniques available for solving the subset sum problem to solve the SGI problem?

推荐答案

是的，你的可以的做到这一点，但每减少已知会产生一个子集和的问题，指数大的数字。

Yes, you could do it, but every reduction known would produce a subset-sum problem with exponentially large numbers.

（此外，btilly，你的功课器坏了。）

(Also, btilly, your homework detector is broken.)