Is “Reachable Object” really an NP-complete problem?

I was reading this paper where the authors explain Theorem 1, which states “Reachable Object” (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. from 2P1N SAT to Reachable Object. This only proves that the problem is NP-hard; do we not need to prove the reverse direction (2P1N to Reachable Object) to prove NP-completeness?

Edit : It was my mistake. “A problem $ \text{Prob}$ is $ \mathbf{NP}$ -complete if $ \text{Prob} \in \mathbf{NP}$ and $ \text{Prob}$ is $ \mathbf{NP}$ -hard” and authors have proved that $ \text{Prob} \in \mathbf{NP}$ as mentioned by dkaeae.

Prove that 2-Independent Set is NP-Complete

The 2-Independent Set problem is a variation of the Independent Set problem in which Given a Graph G=(V,E) does there exist a subset S of V of size atleast k such that for all elements a,b in S the distance between a,b is more than 2.

I want to show that this problem is NP-complete.

My initial idea was to try to reduce from 3-SAT but i am having a hard time figuring out the details.

Is this problem NP-Complete (Bin packing with seperable items and penalty)?

The problem is a bit like bin-packing, so I’ll describe it with similar naming:

  • you have B bins
  • you have two sets of items of cardinality: B*|S_1| = |S_2|
  • all items from the first set, S_1, must be placed in the bins, while items from the second set, S_2, may remain
  • items from set S_2 all have the same value
  • items from the first set can be separated into smaller pieces without restriction
  • for each item piece from S_1 that you place in a bin you must also place another from S_2
  • for all s in S_1 or S_2, 0 < s <= 1, (however, the sizes may be considered discrete to simply the problem) and the size of each bin is 1

Given an instance is it possible to place all elements from S_1 into the bins without exceeding the capacity of the bins?

More simply put: Is bin-packing still NP-Complete if you allow for items to be separated into pieces, but there is a “penalty” for having more pieces in each bin, where for each new piece the bin’s storage constraint decreases by a known amount?

I’ve considered trying to reduce from bin-packing, scheduling, 3-partition, 3-col, 3-SAT, TSP, but I can’t think of a way to do it. Also, in trying to solve the problem in poly. time I can only think of approximation algorithms such as greedily placing the largest item in the bin with the largest remaining capacity.

Any answers or observations on this would be very appreciated.

NP-Complete Problem solved quickly?

I’m probably wrong, but I believed I may have solved a NP-complete problem quickly. I’m having a hard time trying to organize my thoughts for others to understand. So if anyone has a constructive suggestion please let me know with the edit suggestions or the commentary.

Anyway, It is known that if any NP-complete problem can be solved quickly, then every problem in NP can because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every NP-complete problem (that is, it can be reduced in polynomial time).Because of this, it is often said that NP-complete problems are harder or more difficult than NP problems in general. At least according to Wikipedia.

Anyone, who wants an idea of what I was trying to solve please take a look here and take a look at the algorithm down below. I will begin with the explanation of the algorithm.

NOTE: The concept is to visualize the strings as a number line.

The algorithm takes input for a string’s length for L, and the number of strings altogether for X. The hamming distance is for input D. Input Z calculates the exact amount of all possible characters in the string besides the permutations for input D.

We get a set of Z amount of characters. We divide Z by D which is S. We get B possible permutations of characters that can be generated in a list of X strings. In other words, Z divided by Y groupings of the same X should uniquely have B possible permutations within the Z characters. (For the center numerical listed string based on hamming?)

If the algorithm is, correct (or I’ve misled). The center of Z is at the S string which should be the B permutation.

Z = X * X * 1 * L + X * D * D * D + 1   S = Z / D   B = S / D   Y = S / B   CL = D * A ≤ X ≤ B * Y--just for checking   P=B*Y 

More checks

S = S * D / D

D = Z / S

NQ = S / RT P = RT * NQ

Suppose, we have a custom 5th closest string to our primary S which is going to be NQ. We divide NQ by 2 keep adding the sum thereof 5*D until one reaches approximate Z. If it doesn’t equal Z then divide NQ by 2 This will check the algorithm?

Put differently, we have 971 characters altogether in a “superstring.” With these 971 we try to find the 5th closest string. (from 323) We take NQ which is 64.7 and we divide it by 2. Now, 323.6 is our approximated closest string. We take our D which is a 3 hamming distance and multiply it by RT which is 5. We get 15.17. We take 15.17 and multiply it by 64 and we get about 971. 971/5=194.2 We divide it by D and get approximate 3. SO there are 3 other strings that are equivalent to our main solution. To check, we keep subtracting 15 from 971 until we arrive at the closest to 323.

Is this kind of “Gerrymandering” NP-complete?

[I posted this on math.stackexchange.com about two weeks ago, but didn’t get any reply, so I’m trying it here.]

Consider the following simplified form of “Gerrymandering”: You have $ n^2$ squares arranged as an $ n\times n$ matrix. Each square is marked with either $ 0$ or $ 1$ which means a “voter preference” for one of two parties. The task is to divide the set of squares into $ n$ subsets of the same size $ n$ such that one of the parties, say $ 1$ , has the majority in more than half of the regions – if that’s possible at all. The main geometrical restriction is that each region has to be connected, i.e. each square of each region must share at least one edge with at least one other square of the same region.

example picture

I wrote a backtracking algorithm to solve this problem which essentially tries all possible ways of assigning connected regions. It works, but it of course gets much slower as $ n$ increases. I was wondering if this problem (or some variant of it) might be NP-complete. I would think, though, that to be able to find a polynomial-time reduction of a known NP-complete problem to this one, this problem has to be a bit more general. Obviously, there are various ways to generalize it:

  • In its easiest form, the above only works for odd $ n$ as for even $ n$ there’s the chance of a draw. But one could of course also allow draws and stipulate that, say, you’ve “won” in a $ 6\times6$ matrix if you can find three regions with a draw and two where your party wins.
  • One could require that you have to win by a certain margin: $ 1$ needs to win at least $ k$ more regions than $ 0$ .
  • The matrix doesn’t have to be a square matrix.
  • The regions don’t have to have the exact same size.
  • More than two parties…

I would want to keep the connectedness restriction, though.

I searched the web to find similar problems but wasn’t really successful; maybe I didn’t use the right words. I found some results about the math of Gerrymandering, but they are about different (and more complicated) problems. I also tried to find known problems that are obviously related to this one, but so far to no avail. So my questions are:

  • Is this a known problem (maybe a game or puzzle)? And if so, what’s its name?
  • If not, does this look similar to a known problem?
  • Any other hints where to look for more information?

Is the longest Hamiltonian cycle NP-complete?

As I understand it to prove something is NP-complete you have to show that it’s NP-hard by reducing and a known NP-complete problem to your problem and also prove that it is in NP which you do showing that an answer can be verified to be correct in polynomial time.

Now for the longest Hamiltonian cycle in a weighted graph, I know how the reduction would work, but I’m confused about how to verify a solution in polynomial time. To verify that the cycle is Hamiltonian is easy but how would I know if a cycle I’m looking at really is the longest?

Any help would be appreciated!