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
6
votes
1answer
2k views

For what special cases does this vertex cover algorithm fail or work?

I'm trying to find a polynomial time algorithm for finding the minimum vertex cover for a graph. I've written the algorithm below; I know this problem is $\mathsf{NP}$-hard, which means there are ...
6
votes
1answer
2k views

How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
6
votes
1answer
401 views

Modified Clique Problem

We know CLIQUE and HALF-CLIQUE problems are NP-complete. Now consider the class of graphs (let's call it $\mathcal{G}_{2K}$) where a graph $G=(V,E)$ is a member of $\mathcal{G}_{2K}$ iff $G$ has two ...
6
votes
1answer
110 views

Prove TILING is NP-Complete

I have a homework task to show that $\mathrm{TILING} = \{(T, 1^N) \mid \text{it is possible to cover } N \times N \text{ square with tiles from }T\}$, where $t\in T$ is $C^4$ for some color set $C$, ...
6
votes
1answer
926 views

Strongly NP-hard problems and Dynamic Programming

Dynamic Programming seems to result in good performance algorithms for Weakly NP-hard Problems. Two examples are Subset Sum Problem and 0-1 Knapsack Problem, both problems are solvable in pseudo-...
6
votes
1answer
695 views

How to prove that finding math proofs is $\text{NP}$-hard?

This is Exercise 2.11 of the book "Computational Complexity: A Modern Approach" by Arora and Barak. Mathematics can be axiomatized using for example the Zermelo-Frankel system, which has a ...
6
votes
1answer
881 views

NP-complete reduction proof -- graph problem

While studying proofs of NP-completeness via reduction, I saw a seemingly challenging problem: You are given some undirected graph $G = (V, E)$, along with a set $S$ which consists of 0 or more pairs ...
6
votes
1answer
2k views

Reducing directed hamiltonian cycle to graph coloring

The 3-SAT problem can be reduced to both the graph coloring and the directed hamiltonian cycle problem, but is there any chain of reductions which reduce directed hamiltonian cycle to graph coloring ...
6
votes
3answers
3k views

Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete

I'm a little stuck on this question, any help would be appreciated! Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is ...
6
votes
1answer
163 views

Select at least one from each category to minimize union, NP-hard problem?

I have this problem that is very similar to the minimum k-union problem: Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category. The problem is ...
6
votes
1answer
125 views

Partition into paths in a Directed Acyclic Graphs

I have a directed acyclic graph $G=(V,A)$, I want to cover the vertices of $G$ with a minimum number of paths such that each vertex $v_i$ is covered by $b_i$ different paths. When $b_i=1$ for all the ...
6
votes
1answer
99 views

Partitioning bag of sets such that each set in a group has a unique element

Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one ...
6
votes
1answer
138 views

Matrix covering by squares

I wonder about the following decision problem : Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$. Question: is it possible to cover all the ones of the ...
6
votes
1answer
320 views

Path in an edge-weighted undirected graph

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary....
6
votes
3answers
8k views

Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete

I tried to solve the above NP-completeness exercise by making a bipartite graph from a general one (undirected) by inserting a vertice in the middle of every edge of the first (general) graph. This ...
6
votes
1answer
282 views

Is the buckets of water problem in NP?

Continuing from this question: the buckets of water problem. (All the definitions can be found there, so I will not repeat them). As seen there by Yuval's answer, the problem is NP-Hard. I was ...
6
votes
0answers
536 views

What could we say about that conjecture that yields P != NP?

Let $F$ be the set of all Boolean formulae. We say that a Boolean formula $\varphi$ is positive (=monotone) if $\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\...
5
votes
2answers
887 views

Doron ZEILBERGER's P = NP computer proof

In 2009 Doron has published a paper stating "Using 3000 hours of CPU time on a CRAY machine, we settle the notorious P vs. NP problem in the affirmative, by presenting a “polynomial” time algorithm ...
5
votes
3answers
10k views

The relation between 2SAT and 3SAT

Show that proving 2SAT is not NP-Complete would prove that 3SAT is not in P. Or eqivalently - Show that proving 3SAT is in P would prove that 2SAT is NP-Complete. I can see there is an easy ...
5
votes
2answers
693 views

Hardness of mixed 3-SAT and 2-SAT formula

It is well known that 3-SAT is $\sf NP$-complete , but 2-SAT is in $\sf P$. Let there be a formula with $n-1$ clauses with 2 literals each and only 1 clause with 3 literals. We can solve this ...
5
votes
2answers
5k views

How is the Subset Sum Problem NP-Complete?

You can't find a solution online for it that doesn't run in polynomial time complexity, when using dynamic programming. Have all these sites secretly solved P=NP, and no one knows about it?
5
votes
2answers
17k views

Problem A is polynomially reducible to problem B... what can we say about A and B?

This is a question on a practice final. Problem A is polynomially reducible to problem B. Which of the following statements is correct? I. If problem A is solvable in a polynomial time then ...
5
votes
1answer
37k views

Reducing Clique to Independent Set

The Clique problem takes a graph $G = (V,E)$ and an integer $k$ and asks if $G$ contains a clique of size $k$. (A clique is a set of vertices such that every pair of vertices in the set is adjacent.) ...
5
votes
1answer
653 views

NP-Hard problems which are not NP-Complete

Is it always true that a problem which is ${\sf NP}$-hard but not ${\sf NP}$-complete is an optimization problem such as Minimum-Vertex-Cover and many others. Is it always true that a ${\sf NP}$-...
5
votes
3answers
2k views

Prove NP-completeness for union of NP-complete language and language in P

Given disjoint languages $X$ and $Y$, where $X$ is NP-complete and $Y\in P$ , how do I prove that $X\cup Y$ is NP-complete? My idea is to prove that $(X\cup Y)\in NP$ and then prove that $X\cup Y$ is ...
5
votes
2answers
413 views

Is this an instance of a well-known problem?

Context I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I ...
5
votes
1answer
262 views

Prove that $\text{EXACT-TRIPLE}$ is not in NP

I received the following assignment: $\text{EXACT-TRIPLE} = \{ \phi \mid \phi \text{ is a boolean formula that has exactly 3 satisfying assignments} \}$. I need to decide whether this problem ...
5
votes
1answer
4k views

What do we know about $NP \cap co-NP$?

What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it? (beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to ...
5
votes
1answer
712 views

NP-complete decision problems - how close can we come to a solution?

After we prove that a certain optimization problem is NP-hard, the natural next step is to look for a polynomial algorithm that comes close to the optimal solution - preferrably with a constant ...
5
votes
1answer
190 views

Prove that "Finishing the degree in three years" problem is NP-Complete

I was asked in an interview the following question: We'll define the "Finishing the degree in three years" problem in the following manner: Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, ...
5
votes
1answer
468 views

How to show ExactOneSAT is NP-Complete?

$\text{ExactOneSAT}= \{\phi\;|\;\phi\; \text{is a boolean formula}$ $\text{ such that it has a satisfying assignment with only one true literal per clause} \}$ I am trying to reduce 3SAT to this ...
5
votes
1answer
1k views

Is set cover still NP-complete if you have a given k?

Set cover is NP-complete given an arbitrary set $U$, a set $S$ of subsets of $U$, and an integer $k$. However, what if $k$ is always a constant 3? Is that problem still NP-complete?
5
votes
1answer
51 views

What does it mean when $A$ is a NP-Complete Problem but $\bar{A} = NP$?

I'm still in the process of grokking computational complexity. However, I came across a statement like the above in an old midterm paper I'm reviewing, and I'm not sure I completely follow its logic....
5
votes
1answer
137 views

Implication of Berman and Hartmanis conjecture

I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture : All $NP$-Complete languages are $p$-isomorphic. Then the book says that if ...
5
votes
1answer
3k views

Is the set partitioning problem NP-complete?

I know that the set partitioning problem defined like this: Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $\...
5
votes
1answer
265 views

Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?

Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional ...
5
votes
1answer
100 views

Rearrange a sequence of real numbers to satisfy polynomial inequalities

Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$). Consider a list of real numbers $a_1,\ldots,a_n$, does there exist a permutation $\pi$...
5
votes
1answer
783 views

What would an exponential reduction from an NP-complete problem to P signify?

Taking an NP-complete problem like vertex cover if we can find a reduction which is exponential and not polynomial and the reduction we do to a problem can be solved in polynomial time, then what ...
5
votes
2answers
2k views

Reduction to Hamiltonian cycle

Given that the Hamiltonian cycle problem is NP-complete, I want to prove that the following problem is NP-complete: Given an undirected graph $G(V,E)$ and vertices $s,t\in V$, does there exist a ...
5
votes
1answer
170 views

Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to ...
5
votes
1answer
1k views

Pseudo-polynomial time algorithm for NP-Complete Problems

For problems like Knapsack there is a pseudo-polynomial time algorithm and it is NP-complete. So we reduce every other problem in NP in polytime to Knapsack. But why don't we have then a pseudo-...
5
votes
2answers
173 views

Word tiling, where you must use each tile exactly once

Given words $w_1,\ldots,w_n$ in binary alphabet and another word $w$, decide if $w$ can be written as a product $w = w_{i_1} \cdots w_{i_n}$ (in the monoid $\{0,1\}^\ast$) for some permutation of ...
5
votes
1answer
3k views

0/1 Integer Programming and Karp's Reduction

I have been reading Karp's famous paper on the NP-Completeness of different problems, Reducibility among combinatorial problems, and I have a question on the reduction from SAT to 0/1 Integer ...
5
votes
1answer
284 views

How does the problem of having a coffee-machine close relate to vertex cover?

Meeting rooms on university campuses may or may not contain coffee machines. We would like to ensure that every meeting room either has a coffee machine or is close enough to a meeting room that ...
5
votes
2answers
191 views

Is the following NP-complete?

I have encountered the following problem. We have $N$ points in discrete coordinates,distributed through a plane with vertical axis $[1..Y]$ and horizontal axis $[1..X]$. We can perform the action of ...
5
votes
1answer
699 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 ...
5
votes
1answer
638 views

Time complexity of a problem inspired by palindromes

This was inspired by Bradshaw's question originally posted on Math.SatckExchange. EVEN PALINDROME: Input: Given a list of strings $[v_1, v_2, ... ,v_n]$ where $\Sigma |v_i| $ is even number. ...
5
votes
1answer
174 views

What does Cellular Automata Pre-image problem actually means?

I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata. In the 2nd page he lists three NP-Complete ...
5
votes
1answer
2k views

Reduction from PARTITION to MAX-CUT

I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT ...
5
votes
1answer
178 views

Using decision oracle to solve optimization problem of maximum polyomino tiling

So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of ...

1 2 3
4
5
29