Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

Filter by
Sorted by
Tagged with
0
votes
1answer
47 views

Show that a problem is NP-Complete

The problem is, K_longestPath: We are given a graph in which some of the vertices are "cities". No two cities have an edge between them, thus every city must be at distance at least 2 from each ...
-1
votes
1answer
59 views

P Vs NP can never be proven one way or the other!

Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem. And since if we prove that any problem in NP is a P that would mean that we have NP=P. ...
1
vote
1answer
28 views

Encoding order relations in CNF

I want convert timetable scheduling problems to SAT problems. Suppose there are $t$ time slots and $c$ classes. I will define $t\times c$ variables $x_{ij}$, which is true iff class $j$ takes place in ...
-1
votes
0answers
15 views

Translate arbitrary instance to 0/1 Knapsack [duplicate]

How can I translate (i.e. reduce) an arbitrary instance (S,t) of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of S are positive integers.
-1
votes
0answers
22 views

Under the assumption that $P \neq NP$, prove or disprove the following propositions [closed]

I have problem to point 7 and 8. Let $L1,L2 ∈ \{0,1\}^*$. Under the assumption that $P \neq NP$, prove or disprove the following propositions: $L_{1} ∈ P ⇒ L_1^c ∈ NP$. [FALSE] because with $P \neq ...
0
votes
1answer
44 views

triangle inequality TSP is NP-complete?

I have been reading online source and it mentioned triangle inequality TSP is NP-complete but without proof. In general, the reduction from HAM-cycle problem to TSP works for asymmetric and symmetric ...
0
votes
0answers
45 views

If any problem in NP is not in P then NP C ∩ P = ∅

If any problem in NP is not in P then NPC ∩ P = ∅ The proof is: We have $X ∈ NP$ and $X \not\in P$. Assume $Y ∈ NP C ∩ P$. As $X ≤_P Y$ we have $X ∈ P$, which is a contradiction. I have not clear ...
0
votes
0answers
5 views

CPLEX anytime results [closed]

I am working on an NP-Complete problem. When I ran the CPLEX, it gives me only the final solution. I am asking for the help so that I can print the interim results with the time. I am using Python v....
3
votes
1answer
32 views

Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
0
votes
1answer
47 views

NP-completeness for integer linear program

This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come ...
1
vote
1answer
44 views

Independent set problem

I'm referring to a post here,https://www.transtutors.com/questions/suppose-that-someone-gives-you-a-black-box-algorithm-a-that-takes-an-undirected-grap-1706946.htm# Question: Suppose that someone ...
1
vote
2answers
48 views

Prove the Droid Trader Problem is NP-complete

This question is from chapter 8, exercise 35, of Algorithm Design by Kleinberg and Tardos. A player in the game controls a spaceship and is trying to make money buying and selling droids on ...
1
vote
1answer
34 views

Algorithm for idempotent algebra

A boolean algebra expression can be converted into an idempotent algebra using $$\bar a \equiv 1-a, \qquad a \vee b \equiv a+b -ab, \qquad a \wedge b \equiv a \otimes b$$ where $\otimes$ is the ...
2
votes
2answers
218 views

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 ...
-1
votes
1answer
33 views

Another Subset sum problem

Verify that (S = {83, 88, 93, 67, 57, 89, 78, 51, 95, 98, 69, 49}, t = 492) is a positive instance of Susbset Sum.
-2
votes
1answer
41 views

How to find an solution set of subset sum when given an oracle to subset sum problem [closed]

The Subset Sum Problem: Input: a finite subset S of integers, and an integer t. Question: does there exist a subset A ⊆ S such that the members of A sum to t? Suppose you have access to an oracle that ...
1
vote
0answers
19 views

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 $\{ ...
1
vote
1answer
37 views

Subset sum to 0/1 knapsack

How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
0
votes
1answer
34 views

Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it

Is there any known polynomial time algorithm to solve a problem which that problem is in NP. I was told is False but can't think of any counter example now.
1
vote
1answer
30 views

NP Complete Clique Variation

I have the following problem I am trying to prove NP Complete. Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ ...
2
votes
1answer
44 views

Finding a vertex coverage that is also an independent set

Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?
1
vote
1answer
20 views

How to prove that Exact Cover is NP-complete using SAT?

I found this solution online here, but I do not understand the logic behind transforming the instance of SAT to an instance of Exact Cover. Here's the solution from the link (where C is the clause(...
5
votes
1answer
141 views

Using decision oracle to solve optimization problem of maximum polyomino tiling

So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of ...
2
votes
1answer
65 views

If A and B are NP-complete, then A ∪ B need not be NP-complete

I am studying the proof of this exercise (link) There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example: $A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$ $B =...
0
votes
0answers
60 views

Using induction prove that a K-SAT problem is NP-Complete

Using induction on k, how do I prove that the K-SAT problem is NP-complete? On wikipedia, it describes the Cook-Levin theorem to prove that K-SAT is NPC by reducting the K-SAT problem to a circuit-...
1
vote
1answer
38 views

Finishing degree requirements NP-complete: Choosing 1 element from each set avoiding conflicts

The question, which I have slightly paraphrased to get rid of the fat, is this: There are $k$ areas of study in which you need to take 1 course. For each area of study, there is a set of courses $C_1,...
3
votes
1answer
17 views

CNF satisfiability with a bound on number of clauses

Consider the CNF-sat problem with n literals and k clauses. If k scales linearly in n, we get np-completeness (e.g., 3-sat where each literal appears at most 4 times). Do we still get np-completeness ...
1
vote
1answer
32 views

Are all subsets of NP-complete languages also NP-complete?

Is the following assertion true or false? If the language $L$ is NP-complete and $Q ⊆ L$, then $Q$ is NP-complete. I know for example that $k$-coloring is NP-complete if I take $k$ as input, but 2-...
0
votes
1answer
88 views

How to prove Exact cover problem is NP Complete using Vertex Cover problem?

Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from ...
0
votes
1answer
24 views

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 ...
3
votes
1answer
43 views

Given a set, partition it into ordered triples

I have a set $S$ of $3m$ positive numbers $\{a_1,a_2,\ldots,a_{3m}\}$. The question is: can you select $m$ disjoint triples $(a_i,a_j,a_k)$ from $S$ such that $a_i-a_j-a_k\geq1$? I was trying to ...
1
vote
3answers
44 views

How do we construct reductions for NP-Completeness

I'm wondering in what direction we construct reductions to prove that a problem is NP-complete. Say the question is asking to prove that the vertex cover problem is NP-complete given that the ...
0
votes
0answers
32 views

Why does such reductions work [duplicate]

In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS) $V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$ The ...
0
votes
1answer
67 views

How to prove NP-completeness of this variant of the set cover problem?

The problem exactly: Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least ...
5
votes
1answer
95 views

Is finding the minimum feedback arc set on graph with two outgoing 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 ...
1
vote
1answer
25 views

Reductions from non decision problems

I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min ...
2
votes
1answer
30 views

Conditions under which the 3-partition problem is not strongly NP-complete?

I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article: Let B denote the (desired) sum of each subset Si, or equivalently, let the ...
0
votes
2answers
34 views

Decide whether an $n$-bit positive integer is composite

Question: Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP? I know that for every composite number, a factor of the number is a ...
13
votes
5answers
1k views

NP-hard problems but only for n≥3

2-SAT is in P; 3-SAT is NP-complete. Exact cover by 2-sets is in P; exact cover by 3-sets is NP-complete Two-dimensional matching is in P; three-dimensional matching is NP-complete Graph 2-coloring is ...
0
votes
0answers
11 views

What are some counter examples for Load balancing problem?

I learnt about load balancing problem under approximate algorithms. I am learning about it, and studying methods to counter part it's non -solvability under P time. I am quite out of my examples, and ...
0
votes
0answers
25 views

Cook Levin Theorem (Sipser Proof) (phi move)

In Sipser's proof of the cook levin Theorem the move function (phi move) checks whether a given window is legal. For that we must have an exhaustive set of all possible legal windows to verify that a ...
1
vote
0answers
31 views

Partition a multiset into pairs that sum up to given numbers?

Given a multiset of $2m$ positive numbers, $S=\{s_1,s_2,\ldots,s_{2m}\}$ and given $m$ targets $t_1,t_2,\ldots,t_m$. Can we partition $S$ into $m$ pairs $(a_i,b_i)$ such that $a_i+b_i=t_i$, where $a_i\...
5
votes
1answer
80 views

Is GAP NP-hard with at most two balls per bins?

The generalized assignment problem (GAP) [1] is given by: Instance: A pair $(B,S)$ where $B$ is a set of $m$ bins (knapsacks) and $S$ is a set of $n$ items. Each bin $j∈B$ has a capacity $c(j)$, and ...
0
votes
1answer
45 views

Multiple Knapsack Problem with Set of Admissible Balls

We have $m$ bins and $n$ balls. Each bin $i=1,2,\ldots,m$ can contain at most two balls (not any two balls but two balls from some specific set), see 3. Each ball $j=1,2,\ldots,n$ can be put into ...
3
votes
0answers
20 views

Complexity of finding an alternating Hamiltonian (x,y)-path in edge bicolored complete graphs

Let $G$ be a simple complete graph with an edge-2-coloring. An alternating Hamilton (x,y)-path is a Hamiltonian path which starts at vertex $x$ and ends at vertex $y$ such that the colors of its ...
3
votes
1answer
46 views

Complexity of Hamilton path in directed complete bipartite graphs

Finding a Hamiltonian path in a directed bipartite graph is NP-complete. Problem 1 What is the complexity of the problem if we insist that the underlying graph of the digraph be complete ...
4
votes
2answers
102 views

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), ...
0
votes
0answers
43 views

Which is the most similar NP classic problem, if any exists, to this one?

Consider a given set $W = \{w_1, w_2,...,w_N\}$ of weights, such that $\sum_{i=1}^N w_i = 0$. Consider the given set of mutually different elements $A=\{a_1,a_2,...,a_M\}$ with $M\leq N$. Consider the ...
0
votes
0answers
18 views

Subset sum reduction to 3SAT [duplicate]

I have gone over numerous proofs that reduce 3SAT to Subset sum reduction and then claim equivalence, however the other direction is never coherently explained in these proofs. In particular the proof ...
0
votes
1answer
31 views

What to consider while proving NP-completeness?

Suppose that a problem $P$ is known to be NP-hard. The input to the problem is a set of $k$ lines in 2D, a set of $n$ points, and $m < n$ pairwise distances among the points. The goal is to place ...