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
14
votes
1answer
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 ...
14
votes
2answers
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 ...
13
votes
2answers
25k views

Proving DOUBLE-SAT is NP-complete

The well known SAT problem is defined here for reference sake. The DOUBLE-SAT problem is defined as $\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least two ...
13
votes
2answers
4k views

Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

I read about NPC and its relationship to PSPACE and I wish to know whether NPC problems can be deterministicly solved using an algorithm with worst case polynomial space requirement, but potentially ...
13
votes
2answers
3k views

If lower bound of a problem is exponential then is it NP?

Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $\mathcal{\Omega}(2^n)$. can lower bound $\mathcal{\Omega}(2^n)$ implies the problem in $NP$?
13
votes
1answer
2k views

Which NP-Complete problem has the fastest known algorithm?

In terms of worst-case asymptotic runtime, which NP-complete problem has the fastest-known (exact) algorithm and what is the algorithm? Is there something known that is faster than $O(n^2*2^n)$?
13
votes
1answer
1k views

Runtime bounds on algorithms of NP complete problems assuming P≠NP

Assume $P\neq NP$. What can we say about the runtime bounds of all NP-complete problems? i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal ...
13
votes
1answer
642 views

Finding optimal sequence of questions to minimize total student time

Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \{ q_1 \ldots q_k \}$ and a set of $n$ students $S = \{ s_1 \ldots s_n \}$. Each student has a doubt in a ...
12
votes
2answers
1k views

Why does Schaefer's theorem not prove that P=NP?

This is probably a stupid question, but I just don't understand. In another question they came up with Schaefer's dichotomy theorem. To me it looks like it proves that every CSP problem is either in P ...
12
votes
3answers
2k views

Is there an efficient test for if an NFA accepts a subset of another NFA?

So, I know that testing if a regular language $R$ is a subset of regular language $S$ is decidable, since we can convert them both to DFAs, compute $R \cap \bar{S}$, and then test if this language is ...
12
votes
3answers
11k views

All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

My book states this If a decision problem B is in P and A reduces to B, then decision problem A is in P. A decision problem B is NP-complete if B is in NP and for every problem in A in ...
12
votes
1answer
844 views

Are all known algorithms for solving NP-complete problems constructive?

Are there any known algorithms that correctly output "yes" to an NP-complete problem without implicitly generating a certificate? I understand that it is straightforward to turn a satisfiability ...
12
votes
4answers
1k views

Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?

Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded? What difference does it make if the input of a ...
11
votes
1answer
7k views

NP-complete proof from Dasgupta problem on Kite

I am trying to understand this problem from Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, chapter8, Pg281. Problem 8.19 A kite is a graph on an even number of vertices, say $2n$, ...
11
votes
1answer
613 views

Independent set on cubic triangle-free graphs

I know that maximum independent set on cubic triangle-free graphs is NP-complete. Is it still NP-complete in case we require the independent set to be of size exactly $|V|/2$? Basiclly, YES ...
11
votes
1answer
377 views

Can an NP-hard problem be polynomial on average?

I'm wondering if there are any $NP$-hard problems which are ``polynomial" in the average case. I think there are two ways to interpret this? If $P \neq NP$, can there be an algorithm solving an $NP$-...
11
votes
2answers
498 views

Longest cycle contained in two cycles

Is the following problem NP-complete? (I assume yes). Input: $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not a ...
11
votes
0answers
167 views

Covering a complete graph with n copies of an arbitrary graph: NP-complete?

Given a complete graph $G$, an arbitrary graph $H$, and a positive integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that their union is $G$, and each of them ...
10
votes
2answers
3k views

What is wrong with this simple proof of P=NP?

Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiabilty problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
10
votes
2answers
6k views

Do any decision problems exist outside NP and NP-Hard?

This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard. In order to be in NP, problems have to have a ...
10
votes
3answers
594 views

$2k$ number assignment

Given $k$ numbers $A_1 \leq A_2 \leq ... \leq A_k$ such that $\sum\limits_{i=1}^k A_i = k(2k + 1)$ is there an assignment of numbers $i_1, i_2, ... , i_{2k}$ which is a permutation of $1, 2, ... , 2k$ ...
10
votes
2answers
874 views

Is this classic puzzle book game NP-complete?

There is a classic puzzle book game very similar to a crossword puzzle, except a list of words is given and then a $N \times N$ square board made up of unit squares is given, with some squares blacked ...
10
votes
4answers
541 views

A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))

Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE(O(n)) = LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\...
10
votes
1answer
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 ...
10
votes
1answer
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 ...
10
votes
1answer
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 ...
10
votes
1answer
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: ...
10
votes
2answers
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 ...
10
votes
1answer
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\} &...
10
votes
2answers
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 ...
10
votes
3answers
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 ...
9
votes
4answers
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 ...
9
votes
1answer
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$ ...
9
votes
2answers
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 ...
9
votes
1answer
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-...
9
votes
1answer
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 ...
9
votes
2answers
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) ...
8
votes
4answers
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 ...
8
votes
2answers
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$ ...
8
votes
2answers
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. ...
8
votes
1answer
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 ...
8
votes
2answers
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. ...
8
votes
1answer
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 ...
8
votes
2answers
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 ...
8
votes
3answers
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: ...
8
votes
2answers
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$ ...
8
votes
1answer
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 ...
8
votes
1answer
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/...
8
votes
2answers
895 views

Reduction examples from the strongly NPC problem 3-PARTITION

3-PARTITION is strongly NP-complete, i.e. it remains NP-complete even if the input is given in unary. I'm searching two or three examples of (possibly well-known) non-numeric problems that have been ...
8
votes
2answers
175 views

Is an oracle ever useful if you can't control the input instances?

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

1
2
3 4 5
29