## Prove the Droid Trader Problem is NP-complete

This question is from Algorithms Design.

A player in the game controls a spaceship and is trying to make money buying and selling droids on different planets. There are $$n$$ different types of droids and $$k$$ different planets. Each planet $$p$$ has the following properties: there are $$s(j, p) \geq 0$$ droids of type $$j$$ available for sale, at a fixed price of $$x(j, p) \geq 0$$ each, for $$j = 1, 2, \dots , n$$, and there is a demand for $$d(j, p) \geq 0$$ droids of type $$j$$, at a fixed price of $$y(j, p) \geq 0$$ each. (We will assume that a planet does not simultaneously have both a positive supply and a positive demand for a single type of droid; so for each $$j$$, at least one of $$s(j, p)$$ or $$d(j, p)$$ is equal to $$0$$.)

The player begins on planet $$s$$ with $$z$$ units of money and must end at planet $$t$$; there is a directed acyclic graph $$G$$ on the set of planets, such that s-t paths in $$G$$ correspond to valid routes by the player. (G is chosen to be acyclic to prevent arbitrarily long games.) For a given s-t path $$P$$ in $$G$$, the player can engage in transactions as follows. Whenever the player arrives at a planet $$p$$ on the path $$P$$, she can buy up to $$s(j, p)$$ droids of type $$j$$ for $$x(j, p)$$ units of money each (provided she has sufficient money on hand) and/or sell up to $$d(j, p)$$ droids of type $$j$$ for $$y(j, p)$$ units of money (so I’m assuming you can make multiple buy/sells at each planet). The player’s final score is the total amount of money she has on hand when she arrives at planet $$t$$.

I’m trying to prove this problem is harder than some NP-complete problem, but I am quite stuck. Since the planets are organized in a DAG, I think the ‘hardness’ of the problem comes from the fact that you can buy and sell many different types of droids at each planet. Also, this problem is a maximation problem, and I don’t know many NP-complete maximization problems other than quadratic assignment.

Can I get a hint on how to do this? Such as what problem X should I choose to reduce to Droid Trader Problem. Thanks!

Posted on Categories proxies

## How to prove LastToken problem is NP-complete

Consider the following game played on a graph $$G$$ where each node can hold an arbitrary number of tokens. A move consists of removing two tokens from one node (that has at least two tokens) and adding one token to some neighboring node. The LastToken problem asks whether, given a graph $$G$$ and an initial number of tokens $$t(v) \ge 0$$ for each vertex $$v$$, there is a sequence of moves that results in only one token being left in $$G$$. Prove that LastToken is NP-complete.

I’m learning how to prove NP-complete recently but having trouble to understand the concept of NP. As far as I know, to prove a problem is NP-complete, we first need to prove it’s in NP and choose a NP-complete problem that can be reduced from. I’m stuck on which NP-complete problem that can reduce to my problem. As I interpreted this is sequencing problem and I’m guessing I can either reduce Ham Cycle or Traveling Sales Man to my problem, but I don’t see any connection between them so far. How should I start a good approach?

Posted on Categories proxies

## Show that SQUARED-SUM-PARTITION is NP-complete

Consider the following problem SQUARED-SUM-PARTITION. You are given positive integers $$x_1, \dots, x_n$$, and numbers $$k$$ and $$B$$. You want to know whether it is possible to partition the numbers $$\{ x_i \}$$ into $$k$$ sets $$S_1, \dots, S_k$$ so that the squared sums of the sets add up to at most $$B$$: $$\sum_{i=1}^k \left( \sum_{x_j \in S_i} x_j \right)^2 \leq B$$ Show that this problem is NP-complete.

My solution:

We know that the PARTITION problem (Partition a set of numbers into two sets with equal sum) is NP-complete. Let $$S = \{ x_1, \dots, x_n \}$$ be an instance of PARTITION. Let $$T$$ be the sum of all elements in $$S$$. Then we construct instance of SQUARED-SUM-PARTITION by setting $$B = (T/2)^2$$ and $$k=2$$ and $$S$$ remains the same. Then there is a solution for this instance of SQUARED-SUM-PARTITION if and only if there is a solution for PARTITION.

Can I check if this solution is correct? Does anyone have other interesting ways to solve this?

Posted on Categories proxies

## L is NP-complete and L contains an subset Q, then Q is NP-complete (true or false)

I have trouble how to proof "L is NP-complete and L contains an subset Q, then Q is NP-complete" is true or false.

I found online a similar question: "If L contains an NP-complete subset, then L is NP-complete". This question proved false with a counterexample: {0, 1}* ⊃ L_SAT, but {0, 1}*∈P.

I have not clear why {0, 1}* ⊃ L_SAT

Posted on Categories proxies

## Would an optimization version of the 3-partition problem also be strongly np-complete / np-hard?

Anyone know if an optimization variant of the 3-partition problem (as explained there) would also be strongly np-complete?

This would be where the goal is to group a multiset whose size is evenly divisible by 3 into triplets that sum to as close to a target as possible and to produce this grouping. This would not be a decision problem but an actual optimization problem.

Posted on Categories proxies

## Is finding the minimum feedback arc set on graph with two arcs for each node np-complete?

I have a graph with at most two outgoing arcs for each node and i need to extract a dag by removing the least number of arcs. I know that the general problem is np-complete but i can’t reduce it to the other one.

I know that each graph can be mapped to a graph with only two outgoing edges for each node, but i can’t find a way to convert from many edges to two edges that allows me to perform the reduction. If I convert a node with 3 edges to something like

A----B-OUT1 |    | OUT3 OUT2 

Then the mimimun edge set will contain AB instead of B-OUT2 and B-OUT1, provided that OUT1 and OUT2 are generating a cycle, since by cutting AB it will save a point in the objective function.

Is this reduction possible?

Posted on Categories proxies

## correctness of polytime reduction between L1 = ∅ and L2 NP-Complete

Let L1, L2 two language. Suppose L1 = ∅ (I knows also if P = NP ∅ is not NP-complete) and L2 is NP-Complete. Could I polytime reduce L1 to L2 (the other way around is not possible because ∅ is not NP-complete)?.

Posted on Categories proxies

## Are SAT problems with at most two false clauses NP-complete?

Is the problem of deciding whether a SAT instance, where at most two clauses are false (that is, any given variable assignment will either lead to all clauses being true, all but one, or all but two), is satisfiable solvable in polynomial time?

This is a follow-up from my previous question. The problem presented in that question (at most one false clause) was solvable in polynomial time, because we could take advantage of the fact that the set of truth assignments that make a clause false is disjoint to that of any other clause. With two or more clauses, the sets that make a clause false can overlap with each other. Does this mean that problems with at most two (or more) false clauses (when I say “or more,” I do not mean that the number can change with the problem size. A problem with five clauses where at most five are false is a trivial version of regular SAT, but what about a problem of a few million clauses where are most five can be false?) are NP-complete, or are all versions of SAT where you limit the number of false clauses solvable in polynomial time?

Posted on Categories proxies

## Are SAT problems with at most one false clause NP-complete?

Are all SAT instances, where at most one clause is false, solvable in polynomial time? That is, any given variable assignment will either lead to all clauses being true, or all but one. Does such a problem exist? If so, are all instances solvable in polynomial time?

Posted on Categories proxies

## What are the differences between NP-Complete and NP-Hard?

What are the differences between NP, NP-Complete and NP-Hard?

I am aware of many resources all over the web. I’d like to read your explanations, and the reason is they might be different from what’s out there, or there is something that I’m not aware of.

Posted on Categories proxies