NP-Complete reduction (in theory)

Question

I want to embed 3 NP-Complete problems(2 of them are known to be NP-Complete, 1 of them is my own idea). I saw "this question" and got idea about reinterpreting embedding problems in theory:

• The Waiter is The Thief.
• Tables are store.
• Foods are valued items which has different weight.
• Thief know all the items' price and weight before the robbery.
• His target is most efficient robbery(max capacity of knapsack used, most valued items got) with robbing(getting at least 1 item) all stores(shortest way to completing robbery tour, also visit each store 1 time).

This part is embedding 2 NP-Complete problems.

My idea is, that more items mean more bag weight. More bag weight slow downs the thief exponentially. So another target of the thief should be finishing the robbery as quickly as he/she can.

At this time, I'm not sure that my idea is actually NP-Complete. Maybe, "gravity" is not a NP-Complete Problem alone. But maybe it is in this context of the travelling salesman and knapsack problem.

So my questions are:

1. Is the slowing down of the thief NP-complete, too?

2. Is it possible to reduce those three embedded problems to a simple NP-complete problem?

Answer 1

I honestly have no idea what you are asking. But it might be you are asking how you prove one problem NP-complete by converting it to another NP-complete problem.

The answer to this is that you write an algorithm which runs in polynomial time to convert the problem to a known NP-complete problem, then another polynomial algorithm to convert the solution back.

For more details read a decent textbook or see the Wikipedia page.

Answer 2

Okay, that was just a bit tough to follow, but I think I'm getting the gist.

The XKCD cartoon is showing you how easy it is to make a real-life problem NP-complete. (Of course, since most menus have a small number of items and a uniform set of prices, it's also easy to show that there is a trivial answer.)

The idea of "embedding" an NP-complete problem I think you're referring to is finding a poly-time reduction; I've written that up pretty completely elsewhere on SO.

Answer 3

Thanks for helpful comments, Cartoon gave me an idea about embedding problems. I was bit hurry when I was writing, so I did many writing mistakes. My main language is not English too, so editors made my question more understandable. I also want another comments to more brainstorming.

Charlie Martin, thanks for your link.

Answer 4

This is a bit confusing, but here are my answers to some possible questions.

The combination of two NP-complete problems is going to be NP-complete. In fact, the combination of an NP-complete problem with any other problem is going to be NP-complete.

I don't see how to evaluate whether the gravity problem is NP-complete on its own, because it isn't on its own. If the time between points depends on distance as well as backpack weight, then it's NP-complete because it's part of the Traveling Salesman problem. If it doesn't, then the right solution is to pick up objects lightest to heaviest.

The combined problem is a combination of two problems (which objects to steal, and which route to take), and doesn't look any more interesting to me than the two separately, since you can solve one without worrying about the other. Adding weight-dependent delays can couple the problems so they aren't independent, but you need an evaluation function other than how fast you can commit the optimum theft (the optimum theft is its own problem, and then it's just a modified TSP).

Nor are you going to be able to take problems, couple them, complicate them, and then make a simpler problem in general.

Answer 5

The cost of carrying extra weight is not a problem by itself, but rather a parameterization of the edge-weights of your Traveling Salesman Problem.

The decision version of this problem is still NP-complete, because a) we can still check quickly if a given tour has cost less than k so it is in NP, and b) Hamiltonian Cycle still reduces to our TSP with carrying costs (since we just set all edge weights to 1 and all carrying costs to 0 in the reduction).

In other words, the carrying costs just made our TSP harder, so it is still NP-hard (and can be used to solve any NP-complete problem), but it did not make it hard enough that we cannot quickly check a proposed solution to the decision problem: "Does this tour cost less than c?", so it is still NP-complete.

The (NP-complete) decision version of the Knapsack problem is independent, and can be solved sequentially with the TSP problem.

So the entire problem is NP-complete, and if we reduce the TSP problem and the Knapsack problems to SAT (reduction normally isn't done in this direction but it is theoretically possible), then we can encode the two together as one SAT instance.