All geek questions in one place

NP-total contraction (theoretically)

I want to include 3 NP-Complete problems (2 of them are NP-Complete, as you know, 1 of them is my own idea). I saw " this question " and got an idea about the theoretical problems of re-interpretation of investments:

  • The waiter is a thief.
  • Tables are storage.
  • Food is valuable items that have different weights.
  • A thief knows all the prices and weight of items before the robbery.
  • Its goal is the most effective robbery (maximum backpack capacity, the most valuable items) with robbery (getting at least 1 item) of all stores (the shortest way to end the robbery tour, also visiting each store 1 time).

This part is embedded in 2 NP-Complete problems.

My idea is that more items mean more bag weight. More bag weight slows the thief exponentially. Thus, another thief's goal should end with robbery as fast as he can.

At this time, I'm not sure that my idea is actually NP-Complete. Maybe gravity is not the only problem with NP-Complete. But perhaps it is in this context that the problem of a traveling salesman and a satchel.

So my questions are:

  • Is thief moderation also NP-complete?

  • Can these three built-in tasks be reduced to a simple NP-complete problem?

+3
source share
5 answers

Well, that was a bit complicated, but I think I'm getting the gist.

XKCD , NP-. (, , , .)

"" NP- , , ; SO.

+2

, .

NP- NP-. , NP- NP-.

, , NP- , . , , NP-complete, Traveling Salesman. , , , .

( ), , , , , , , , , ( - , TSP).

, , , .

+1

, . , , , NP-, NP-.

, , , NP- , .

.

0

, . , , . , . , " ".

, .

0

, .

- NP-, : ) , k, NP, b) - TSP ( 1 0 ).

, TSP , - NP-hard ( NP-), , : " , c?", - NP-.

The NP-complete solution to the Knapsack problem solution is independent and can be resolved sequentially with the TSP task.

So, the whole problem is NP-complete, and if we reduce the problem of TSP and Knapsack problems with SAT (reduction is usually not performed in this direction, but this is theoretically possible), then we can encode the two together as one instance of SAT.

0
source

Source: https://habr.com/ru/post/1703116/

More articles:


All Articles