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

### Approximation of minimum bandwidth on binary trees

Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. The decision problem is NP-complete even for ...
3k views

### Reduction from 3-Partition problem to Balanced Partition problem

The 3-Partition problem asks whether a set of $3n$ integers can be partitioned into $n$ sets of three integers such that each set sums up to some given integer $B$. The Balanced Partition problem asks ...
25k views

1k views

### Pebbling Problem

Pebbling is a solitaire game played on an undirected graph $G$ , where each vertex has zero or more pebbles. A single pebbling move consists of removing two pebbles from a vertex $v$ and adding ...
2k views

### Showing that minimal vertex deletion to a bipartite graph is NP-complete

Consider the following problem whose input instance is a simple graph $G$ and a natural integer $k$. Is there a set $S \subseteq V(G)$ such that $G - S$ is bipartite and $|S| \leq k$? I would like ...
1k views

### Intuition behind Relativization

I take course on Computational Complexity. My problem is I don't understand Relativization method. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will ...
221 views

### Could this be an NP-Complete problem?

Consider the following problem statement: Given an initial number, you and your friend take turns to subtract a perfect square from it. The first one to get to zero wins. For example: ...
2k views

### Can we construct a Karp reduction from a Cook reduction between NP problems?

We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as ...
320 views

### Hardness of approximating 0-1 integer programs

Given a $0,1$ (binary) integer program of the form:  \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} &...
2k views

### NP-Completeness of a Graph Coloring Problem

Alternative Formulation I came up with an alternative formulation to the below problem. The alternative formulation is actually a special case of the problem bellow and uses bipartite graphs to ...
351 views

### Is connecting islands with pontoons NP-complete?

I have a problem in my mind, I think it is a NPC problem but I don't know how to prove it. Here is the problem: There are k islands in a very big lake, and there are n fan-shaped pontoons. Those ...
4k views

### How are all NP Complete problems similar?

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified ...
27k views

### Why is the clique problem NP-complete? [duplicate]

Possible Duplicate: Is the k-clique problem NP-complete? I've been lately reading about the clique problem, specifically, the variety of the clique problem of deciding whether a given graph $G$ ...
581 views

### Prove that the 2-approximation of a modified local search algorithm for max-cut is tight

Consider the following local search approximation algorithm for the unweighted max cut problem: start with an arbitrary partition of the vertices of the given graph $G = (V,E)$, and as long as you ...
5k views

### Is the 0-1 Knapsack problem where value equals weight NP-complete?

I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of 0-1-...
5k views

### Negative numbers in Subset-Sum

If I have a set $A$ with positive and negative numbers, and a number to find C. It is possible to reduce the problem to one with only positive numbers in set $A$? I mean, it is possible to find a ...
7k views

### Algorithms for two and three dimensional Knapsack

I know that the 2D and 3D Knapsack problems are NPC, but is there any way to solve them in reasonable time if the instances are not very complicated? Would dynamic programming work? By 2D (3D) ...
4k views

### Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?

I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists. Is there a good / quick / easy way to see ...
624 views

### What is a dichotomy? Whether 2-SAT itself is a dichotomy of SAT?

Recently, I am reading papers about dichotomy. I do not understant what condition can be called as a dichotomy? What is the meaning of "a question is either in P or in NP-complete"? (assume P $\neq$ ...
2k views

### Is "Reachable Object" really an NP-complete problem?

I was reading this paper where the authors explain Theorem 1, which states "Reachable Object" (as defined in the paper) is NP-complete. However, they prove the reduction only in one direction, i.e. ...
1k views

### Is there a simple argument why graph isomorphism is not NP-complete?

I need to provide one simple evidence that graph isomorphism (GI) is not NP-complete. I saw a number of papers on google scholar and answers on StackExchange. However, I have very limited knowledge of ...
15k views

### are NP Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. ...
514 views

### Partition problem with distinct integers

The partition problem is a well-known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers, and we want to decide the existence of a partition into ...
4k views

### Typical NP-complete/hard problems in machine learning

I know little about machine Learning, but I work on optimization (solving NP-hard problems with SAT solvers or MIP). Examples of this would be solving TSP, Steiner tree problems, path finding with ...
21k views

### How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?

3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring: ...
888 views

### Why doesn't Godel's Second Incompleteness Theorem rule out a formalizable proof of P!=NP?

I'm sure there must be something wrong with the following reasoning because otherwise a lot of P vs. NP research would be curtailed but I cannot determine my error: For any fixed integer $k>0$ ...
8k views

### Proof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)

I need to prove that TAUT is coNP-complete. I showed that $\text{TAUT} \in \text{coNP}$ by reducing $\text{SAT}$ to $\overline{\text{TAUT}}$. However, I cannot figure out how to prove that every ...
6k views

### 3-SAT for variables appearing 3 times

I've been trying to investigate 3-SAT for variables appearing 3 times and so far I'm getting some mixed answers as to its complexity. For example, https://people.maths.ox.ac.uk/scott/Papers/...
Let's say $F$ is an oracle for a problem in $\mathbb{NP}$, but I cannot call this oracle with any input instance. Instead, whenever I call $F$ I get returned a random instance and solution. Thus, I ...