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

### NP-Complete reductionTrue/False question explanation

Why is the above statement true? my understanding is: (1)3SAT reduces to X implies X is NP-complete or harder. (2)Set Cover reduces to X implies X is neither NP-Complete nor harder. This ...
52 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 ...
40 views

### Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k) polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a ...
35 views

### In which paper is written that you can transform one problem to another to show NP-completeness?

For example in this post they discuss how to construct a reduction between problems to show that one probleme is NP-Hard: Post I am searching for a scientific paper to cite where it is written, that ...
122 views

### What is wrong with the following $P$ problem?

Our teacher gave us the following statement and we were wondering what is wrong with it. Consider an array $A$ of $n$ distinct numbers. Since there are $n!$ permutations of $A$, we cannot check ...
55 views

39 views

### A variant of the knapsack problem

Consider the following variant for the knapsack problem: the input are disjoint sets of items $T_1, T_2, ..., T_m$ (each contains items of a different type). Every item $i$ has a value of $v_i$ and a ...
28 views

### how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then ${NP = P ? }$
24 views

### Looking for some references on voting theory

After reading through this paper on optimizing the sum of sigmoid functions, http://www.web.stanford.edu/~boyd/papers/pdf/max_sum_sigmoids.pdf, I am interested in the problem addressed in section 7.3 ...
12 views

### What is the FPTAS algorithm to find flow at each link for multi commodity flow problem?

I have a graph and K commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodity and the relevant paths. I understand the problem in ...
24 views

### Strongly connected subgraph that contains no negative cycles

Is there an efficient algorithm that solves the following decision problem: Given a strongly connected weighted directed graph $G$, defined by its transition matrix, is there a strongly connected ...
20 views

### Clarifying what it means to be Strongly NP-Complete

Wikipedia defines strongly NP-Complete as: A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the ...
29 views

### Disjoint paths in digraphs is NP-complete

In the article: S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraphs homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111–121. link: https://www.sciencedirect.com/science/article/pii/...
31 views

### How to know if a problem belongs to NP Class?

What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we ...
125 views

223 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 ...
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.
19 views