# 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,103 questions
Filter by
Sorted by
Tagged with
41 views

### Two versions of Subset Sum Problem

I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is: Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, ...
67 views

### An NP-hard problem reduces to its complement?

I found this statement in a true/false test section: Could someone explain in laymans why this is a true statement? My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must ...
19 views

### Minimum total waiting time for arrivals/durations

I have come up with the following problem, and cannot seem to find an effective way of solving it: Consider $n$ clients arriving at a service point at time moments $\{a_i\}_{i=1}^n$ whose duration ...
7k views

### P = NP clarification

Let's use Traveling Salesman as the example, unless you think there's a simpler, more understable example. My understanding of P=NP question is that, given the optimal solution of a difficult problem,...
6 views

### Are all NP-complete languages downward self-reducible?

Arora-Barak says that using the Cook-Levin reduction, one can show that all NP-complete problems are downward self-reducible. I know that SAT is downward self-reducible but I am not able to see how we ...
24 views

### Obtaining a graph with no cycles after removing k edges

I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
38 views

### Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

i don't understand the following: If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
18 views

### polynomial reduction & co np complete

I would like to know how we can demonstrate these two problems : $A \leqslant_p B$ implies $\overline A \leqslant_p \overline B$ The complement of 3-SAT is co-NP-complete
39 views