reductions – If problem A reduces to an NP-Complete problem B, can we say that A is in NP?

I was reviewing All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

I understand that the general way we show a problem A is in NP is to show there exists a poly-time certifier for A. However, I am confused if say, we know nothing about A, and it reduces to an NP-Complete problem B, can we now say that A is in NP?

I understand that all problems in NP reduce to any NP-Complete problems, but I’m not sure if this will prove anything. I also understand to show a problem is NP-Complete, we first show it’s in NP with a poly-time verifier/certificate and then reduce an NP-Complete problem to it. But confused about this other scenario:

Let A be an unknown problem.
Let B be a known problem in NP-Complete.
A reduces to B
What does this tell us about A?

Is A and C NP-complete?

Given 3 decision problems in $NP$: $A,B,C$.
Consider that there are $2$ reduction algorithms, one is $Ale_p B$ (with run-time $n^{10}$) and the other is $Ble_p C$ (with run-time $n^5$).

If $B$ is $NP-complete$, is it valid to say that $A$ and $C$ are also $NP-complete$?

Is this explanation confusing NP-hard and NP-complete?

My notes on P vs NP say the following:

Every problem x in the NP-hard class has the following properties:
– There is no known polynomial-time algorithm for x.
– The only known algorithms take exponential time.
– If you could solve x in polynomial-time, then you could solve them all in polynomial-time.

The last point sounds like it’s confusing NP-hard with NP-complete. I would appreciate it if someone would please clarify this.

complexity theory – How to prove this josephus problem variation is a np-complete or np-intermediate problem?

have a problem that is a Josephus problem variation. It is described below:

There are m cards with number from 1 to m,and each of them has a unique number. The cards are dispatched to n person who sit in a circle. Note that m >= n.

Then we choose the person “A” who sits at the position “p” to out of the circle, just like the Josephus problem does. Next step we skip “k” person at the right of p while k is the number of the card toked by the person “A”, and we do the same thing until only one person left in the circle.

Question is given n person and m cards, can we choose n cards and allocate them to the n person, to make that whether start at which position(exclude the first position), the person survival at the end is always the first person in the circle.

For example, m = n = 5, the only solution is (4, 1, 5, 3, 2).

I think this problem is a np-complete or np-intermediate problem, but I can’t prove it. Anybody has a good idea to find a polynomial time solution or prove it’s np-hard?

— example solutions —

 2: ( 1,  2)
 2: ( 2,  1)
 3: ( 1,  3,  2)
 3: ( 3,  1,  2)
 4: ( 4,  1,  3,  2)
 5: ( 4,  1,  5,  3,  2)
 7: ( 5,  7,  3,  1,  6,  4,  2)
 9: ( 2,  7,  3,  9,  1,  6,  8,  5,  4)
 9: ( 3,  1,  2,  7,  6,  5,  9,  4,  8)
 9: ( 3,  5,  1,  8,  9,  6,  7,  4,  2)
 9: ( 3,  9,  2,  7,  6,  1,  5,  4,  8)
 9: ( 6,  1,  8,  3,  7,  9,  4,  5,  2)
10: ( 3,  5,  6, 10,  1,  9,  8,  7,  4,  2)
10: ( 4,  5,  2,  8,  7, 10,  6,  1,  9,  3)
10: ( 5,  1,  9,  2, 10,  3,  7,  6,  8,  4)
10: ( 6,  3,  1, 10,  9,  8,  7,  4,  5,  2)
10: ( 8,  5,  9, 10,  1,  7,  2,  6,  4,  3)
10: (10,  5,  2,  1,  8,  7,  6,  9,  3,  4)
11: ( 2,  1, 10, 11,  9,  3,  7,  5,  6,  8,  4)
11: ( 3,  7, 11, 10,  9,  8,  1,  6,  5,  4,  2)
11: ( 3, 11, 10,  9,  8,  1,  7,  2,  4,  5,  6)
11: ( 4,  1, 10,  2,  9,  8,  7,  5, 11,  3,  6)
11: ( 4,  2,  7, 11,  5,  1, 10,  9,  6,  3,  8)
11: ( 4,  7,  2,  3,  1, 10,  9,  6, 11,  5,  8)
11: ( 4,  7,  3,  9, 11, 10,  1,  8,  6,  5,  2)
11: ( 4, 11,  7,  2,  1, 10,  9,  6,  5,  3,  8)
11: ( 5, 11,  3,  9,  8,  7,  6,  1, 10,  4,  2)
11: ( 6,  1, 10,  2,  9,  8,  7,  5, 11,  3,  4)
11: ( 6,  2,  7, 11,  5,  1, 10,  9,  4,  3,  8)
11: ( 6, 11,  1,  3, 10,  2,  7,  5,  4,  9,  8)
11: ( 9,  5,  3,  1, 10,  2,  8,  7, 11,  6,  4)
12: ( 1,  7, 11, 10,  4,  9,  2, 12,  6,  5,  8,  3)
12: ( 3,  7, 12,  2, 11, 10,  9,  1,  6,  5,  4,  8)
12: ( 3,  8, 11,  2, 12,  9,  1,  7,  5, 10,  4,  6)
12: ( 4,  2,  5,  1, 11, 10,  9,  8, 12,  7,  3,  6)
12: ( 4,  3,  7,  6,  1, 11, 10,  9,  8, 12,  5,  2)
12: ( 5,  1,  6, 11,  9,  2, 10,  7, 12,  8,  3,  4)
12: ( 5,  2,  3, 12,  9, 10,  7,  6,  1, 11,  4,  8)
12: ( 5,  7, 12,  2, 10,  9,  8, 11,  1,  4,  6,  3)
12: ( 7,  1,  2,  3,  5,  9, 10,  8, 11,  6, 12,  4)
12: ( 8,  7,  1, 11,  9,  3,  5, 10,  6,  4, 12,  2)
12: ( 8,  7, 11, 10, 12,  3,  1,  9,  6,  5,  4,  2)
12: (12,  3, 11,  5,  1, 10,  8,  7,  6,  4,  9,  2)
12: (12,  7, 11,  1,  9,  3,  2, 10,  6,  5,  4,  8)
13: ( 2,  1,  4,  7, 11,  6,  3, 10, 13,  5,  8, 12,  9)
13: ( 2,  5, 13, 12,  4, 11,  3,  1,  9,  7,  8,  6, 10)
13: ( 2, 13, 12, 11,  3,  1,  9,  4,  8,  7, 10,  5,  6)
13: ( 3,  5,  2,  1, 12,  9, 11, 10,  7,  6, 13,  4,  8)
13: ( 3,  5, 13,  1, 11,  2,  9,  8,  7, 12,  6,  4, 10)
13: ( 4, 13,  3,  1, 12, 11, 10,  9,  7,  2,  5,  6,  8)
13: ( 6,  4,  3,  1, 10, 11, 13,  5,  9, 12,  7,  8,  2)
13: ( 6,  4, 13,  7,  5,  1, 12, 11, 10,  9,  8,  3,  2)
13: ( 6,  7,  3, 13, 12, 11, 10,  2,  1,  9,  5,  4,  8)
13: ( 6,  7, 13, 11,  2, 10,  9,  1,  8, 12,  5,  3,  4)
13: ( 6, 11,  7, 13,  1, 10,  2, 12,  9,  8,  5,  4,  3)
13: ( 7,  3,  2,  1, 11, 10,  9,  8, 13,  5, 12,  4,  6)
13: ( 7,  5, 13,  3, 10, 11,  2,  9,  1,  6,  8,  4, 12)
13: ( 7,  5, 13,  3, 11,  2,  9,  8,  1,  6, 12,  4, 10)
13: ( 7,  5, 13,  3, 11, 12,  2,  1,  9,  8,  6,  4, 10)
13: ( 7,  9,  1, 11,  3, 13,  2, 10, 12,  6,  5,  4,  8)
13: ( 8,  3,  5, 11, 13,  9, 10,  7,  1,  6,  4, 12,  2)
13: ( 8,  3, 13,  1,  5, 11, 10,  9, 12,  7,  6,  4,  2)
13: ( 9,  3, 13,  2, 10,  4,  1,  7,  6,  5, 12, 11,  8)
13: ( 9,  4,  7,  5,  1, 11, 13, 10, 12,  8,  6,  3,  2)
13: ( 9,  5,  4, 13,  2, 11,  8, 10,  1,  7, 12,  3,  6)
13: ( 9,  5, 13,  4, 11,  1,  8,  3,  7, 12,  6, 10,  2)
13: (10,  4,  3,  5, 13,  1,  9, 11,  7,  6,  8, 12,  2)
13: (11,  2,  7,  3, 12,  1, 10,  9,  6,  5, 13,  4,  8)
13: (11, 13,  5,  2, 10,  9,  8,  7,  1,  6,  4,  3, 12)
13: (11, 13,  7,  1, 12,  9,  2,  3, 10,  5,  4,  6,  8)
13: (12,  1,  3,  5, 11, 13,  4, 10,  9,  8,  7,  6,  2)
13: (12,  7, 13,  3, 11,  1,  9,  8,  6,  5, 10,  4,  2)
13: (12, 13,  7, 11,  2,  5,  1,  9, 10,  6,  4,  3,  8)
13: (13,  3,  1, 12, 11,  2,  9, 10,  7,  6,  4,  5,  8)
13: (13,  3,  7,  1,  5, 12,  4, 10,  9,  8, 11,  6,  2)
14: ( 3,  5, 13, 14,  1, 12, 11, 10,  9,  8,  7,  6,  4,  2)
14: ( 3,  9,  1, 13, 11, 10,  2,  4,  7, 14,  6,  8,  5, 12)
14: ( 3, 14,  4, 12, 11,  1,  9,  8,  2, 13,  7,  5, 10,  6)
14: ( 4, 11,  1, 13,  7, 10, 12,  2, 14,  9,  8,  5,  6,  3)
14: ( 4, 14,  2,  5, 13,  1, 12, 11,  7,  6, 10,  9,  3,  8)
14: ( 5,  7,  1, 13, 12, 11, 10,  2,  9,  8, 14,  6,  4,  3)
14: ( 6,  3, 14,  5, 11, 13,  2, 12,  9,  1,  7,  4,  8, 10)
14: ( 6, 14,  1, 12,  5, 13,  2, 11,  9,  7,  8,  4,  3, 10)
14: ( 7,  5, 13, 12,  1, 11,  4, 10,  2, 14,  9,  8,  6,  3)
14: ( 7, 11,  5, 13,  1,  3,  2,  4, 10,  9, 14,  6,  8, 12)
14: ( 7, 14,  1, 13,  2,  5, 11, 12, 10,  9,  8,  4,  3,  6)
14: ( 8,  7,  5, 13,  2, 11,  3,  9, 10, 12,  1, 14,  4,  6)
14: (11,  2, 10,  5,  8,  7,  9,  1, 13, 14, 12,  4,  3,  6)
14: (11,  3, 14,  2, 13,  1, 10,  8,  9,  7,  5, 12,  4,  6)
14: (11,  5,  3, 14,  2,  1, 13, 10,  8,  7,  6, 12,  4,  9)
14: (11, 14,  5,  3, 13,  1, 10,  2,  9,  4,  7,  8, 12,  6)
14: (12,  1, 14,  3, 13,  4, 10,  9,  2,  7,  6,  5, 11,  8)
14: (12, 11,  7,  5, 13,  3,  2, 14,  1,  9,  8,  4,  6, 10)
14: (12, 14,  7, 13,  6,  5, 11,  1, 10,  9,  8,  4,  3,  2)
14: (13,  1,  7,  2, 11,  3,  9, 14,  8,  6,  5, 10,  4, 12)
14: (13, 11,  3,  1,  4,  2,  7, 10,  9,  6, 14, 12,  5,  8)
14: (14,  1, 13,  3, 11,  5, 10,  9,  2,  6,  8,  7,  4, 12)
14: (14, 5, 1, 13, 12, 2, 11, 3, 7, 9, 6, 8, 4, 10)

Research on exact-cover problem and graph theory for NP-complete problems?

Sorry for the vagueness, but I’m trying to study the latest progress on the exact cover problem and using graphs for NP-complete problems. Googling around has not been very helpful. I understand the basics but I can’t find a key journal in this area or where to look online. Any references would be greatly appreciated!

time complexity – Betweenness Problem for Binary Comparisons is NP-Complete

I have a very simple question and wanted to check whether my answer is correct.

Suppose we are given a list of comparisons $x_1>x_2,..,x_k>x_i$ then consider the decision problem asks whether the ordering $>$ can be made transitive and complete over all the X.

My impression is that such a decision problem is NP-complete. Here is my proposed solution.

  1. Any solution can be checked in polynomial time, suffice to verify each comparison from the solution ordering.
  2. To show it is NP-complete, I show that the Betweenness Problem with triple type (https://en.wikipedia.org/wiki/Betweenness) is reducible to ours.

Proof of 2):
The Betweenness problem asks exactly our question but has ordering of type $x_1>x_2>x_3$.
But of course each such statement can be translated to $x_1>x_2$, $x_2>x_3$ this is done in at most (?) than polynomial time.

I just wanted to check whether this solution is correct and complete? Any help is greatly appreciated, thanks a lot!

satisfiability – Is the following problem NP-Complete?

No. This problem is equivalent to XOR-3SAT, in which we interpret each clause as $x oplus y oplus z$, where $oplus$ is the XOR operator, and ask whether it’s possible to find values for all variables so that each clause is true. XOR-SAT can be solved in polynomial time using Gaussian elimination, with all arithmetic done modulo 2 (i.e., in the finite field $GF(2)$).

Reducing a P-complete search problem to an NP-complete decision problem

Let us say that a search problem $R$ has an A-reduction if there is a polynomial algorithm $A$ that solves $R$ using an oracle to the decision problem $S_R$, so that for each input $x$, the number of oracle calls that $A$ makes is at most $100log|x|$.

Assume that $P ne NP$. Prove or disprove:
There is a search problem $R in FNP$ so that $S_R$ is $NPC$ and $R$ has an A-reduction.

I am a bit confused about what “at most $100log|x|$” means. I also don’t know how to find a search problem $R$ that satisfies the requirement.

Show that this problem is NP-complete

I need some help with the following question.

SHIP LOADING: Given items of weights x1,…,xn, ships of weight
capacity B, can the items be loaded onto C or fewer ships? (All
numbers are positive integers, given in binary.)

Show that SHIP LOADING is NP-complete. (Hint: reduce from SUBSET SUM,
but go through a restricted version where the target b is half the
total.)

complexity theory – Consequence of NP-complete, and DP-complete w.r.t. randomized reductions

If a problem is NP-complete with respect to randomized (polynomial time) reductions, but not with respect to deterministic reductions, then we have P $neq$ BPP (See Question 2 here and its answer).

Suppose a decision problem is proved to be NP-complete; and it is also proved to be DP-complete with respect to randomized reductions. Does this have any real consequence?

Context
Given a graph $G$, it is coNP-complete to test whether $G$ has exactly one 3-colouring upto swapping of colours (because the “another solution” problem associated with 3-colouring is NP-complete (1)). The same problem is DP-complete with respect to randomized reductions (2).

(1) Dailey, David P., Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Discrete Math. 30, 289-293 (1980). ZBL0448.05030.

(2) Barbanchon, Régis, On unique graph 3-colorability and parsimonious reductions in the plane, Theor. Comput. Sci. 319, No. 1-3, 455-482 (2004). ZBL1043.05043.