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

338 views

### Given a truth table, force a contradiction

Suppose I have a formula, and a lying witness is attempting to make it evaluate to False. Given a truth table $c(F_1,…, F_n)$, how could you force a lying witness to contradict herself? A ...
37k views

### How can I reduce Subset Sum to Partition?

Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to Partition but at this time I don't see the relation! Is it possible to reduce this problem ...
1k views

### Hardness and directions of reductions

Let us say we know that problem A is hard, then we reduce A to the unknown problem B to prove B is also hard. As an example: we know 3-coloring is hard. Then we reduce 3-coloring to 4-coloring. By ...
2k views

### Planarity conditions for Planar 1-in-3 SAT

Planar 3SAT is NP-complete. A planar 3SAT instance is a 3SAT instance for which the graph built using the following rules is planar: add a vertex for every $x_i$ and $\bar{x_i}$ add a vertex for ...
163 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 ...
2k views

### complexity of decision problems vs computing functions [closed]

This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens ...
183 views

### Creating artificial NP-Complete problems

Stephen Cook's proof of the NP-completeness of SAT is constructive. Given a Turing machine $M$, one can create a logical formula that is satisfiable if and only if $M$'s computation halts in an ...
4k 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$, ...
7k views

### Reduction from set cover problem to vertex cover problem

Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I ...
256 views

### Find small superset of at least k of n given sets

Say we're given $n$ sets and the size of their union is $m$. We would like to construct a small set which contains at least $k$ of the $n$ given sets. Lets assume that $m$ is less than some ...
3k views

### Types of reductions and associated definitions of hardness

Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. ...
322 views

### $L$ APX-hard thus PTAS for $L$ implies $\mathsf{P} = \mathsf{NP}$

If $L$ is an APX-hard language, doesn't the existence of a PTAS for $L$ trivially imply $\mathsf{P} = \mathsf{NP}$? Since for example metric-TSP is in APX, but it is not approximable within 220/219 ...
2k views

### Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT

In Cormen's Algorithms book on NP-completeness they prove various problems are NP-complete by reducing a previously proved NP-complete problem (call $K$) to current problem (call $L$). Each proof ...
3k 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 ...
261 views

### Can an exponential algorithm for an NPC problem be transformed into an algorithm for other NP problems in polynomial time?

After looking at other questions and my textbook, I seem to get some confusion. I do get that when there is a polynomial algorithm of NPC, there is a polynomial algorithm for a NP problem. But the ...
3k 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 ...
20k views

### How can I verify a solution to Travelling Salesman Problem in polynomial time?

So, TSP (Travelling salesman problem) decision problem is NP complete. But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is ...
1k views

### A polynomial reduction from any NP-complete problem to bounded PCP

Text books everywhere assume that the Bounded Post Correspondence Problem is NP-complete (no more than $N$ indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something ...
827 views

### Is SAT in P if there are exponentially many clauses in the number of variables?

I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$. I'd like to know ...
268 views

### Vertex coloring with an upper bound on the degree of the nodes

Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices ...
270 views

### The $\text{k-key}$ problem

Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well. Here's the k-key problem: ...
7k views

### Is finding the longest path of a graph NP-complete?

The problem of finding the largest subgraph of a graph that has a Hamiltonian path can be restated as finding the longest path of a graph. Is this NP-complete? Also, is finding the $k$-length path of ...
187 views

### How do we distinguish NP-complete problems from other NP problems?

I just learned that when we have a polynomial algorithm for NP-complete problems, it is possible to use that algorithm to solve all NP problems. So, the question is how we then distinguish non-NP-...
620 views

### NP-completeness of graph isomorphism through edge contractions with an edge validity condition

Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ...
170 views

### Proof of NP-completeness of graph isomorphism through edge contractions that reduce a metric [duplicate]

Duplicate: NP-completeness of graph isomorphism through edge contractions with an edge validity condition I know that graph contractability is $NP$-complete. To be specific given $G=(V_1,E_1)$ ...
254 views

### Does a collision oracle for the pigeonhole subset sum problem produce solutions?

I am reading "Efficient Cryptographic Schemes Provably as Secure as Subset Sum" by R. Impagliazzo and M. Naor (paper) and came across the following statement in the proof of Theorem 3.1 (pages 10-11): ...
322 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 ...
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 ...
489 views

### Does every NP problem have a poly-sized ILP formulation?

Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ...
9k views

### Rule of thumb to know if a problem could be NP-complete

This question was inspired by a comment on StackOverflow. Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like ...
22k views

### Are there NP problems, not in P and not NP Complete?

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but ...
253 views

### From FACTOR To KNAPSACK

If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently, could one not also use this algorithm to solve unbounded ...
2k views

### Is Logical Min-Cut NP-Complete?

Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
6k 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) ...
5k views

### Dealing with intractability: NP-complete problems

Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
1k views

### Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs

I'm trying to solve a problem for class that is stated like so: A bipartite graph is an undirected graph in which every cycle has even length. We attempt to show that the Hamiltonian cycle (a ...
3k views

### NP-completeness of a spanning tree problem

I was reviewing some NP-complete problems on this site, and I meet one interesting problem from NP completeness proof of a spanning tree problem In this problem, I am interested in the original ...
8k views

### How do I construct reductions between problems to prove a problem is NP-complete?

I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How ...
10k views

### HALF CLIQUE - NP Complete Problem

Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please. With that said, here is the problem I am looking at: Let HALF-...
1k views

### Subset-sum and 3SAT

Two things (this may be naive): Does anyone believe there is a sub-exponential time algorithm for the Subset-sum problem? It seems obvious to me that you would have to look through all possible ...