# 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.

1,068 questions
Filter by
Sorted by
Tagged with
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 ...
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. ...
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 ...
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.
22 views

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.
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.
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$ ...
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?
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(...
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 ...
65 views

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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...