Hot answers tagged

38 votes
Accepted

Hardness of a problem which is the sum of two NP-Hard problems

Nothing. Lower bound: Suppose $h(x) = -f(x)$. Then $\sum_x g(x) = 0$, which is trivial to compute. If $\sum_x f(x)$ is NP-hard to compute, then $\sum_x h(x)$ will be too, but $\sum_x g(x)$ will be ...
  • 145k
18 votes
Accepted

Is the following problem NP-hard? (or have you seen it before?)

This problem (more formally its decision version) is NP-complete. NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be ...
  • 296
17 votes
Accepted

Is detecting easy instances of NP-hard problems easy?

The problem isn't really well-posed. For any particular instance, there is a single solution, say $S$. Consequently, we can imagine an algorithm that has the answer $S$ hardcoded in: no matter what ...
  • 145k
17 votes
Accepted

Why rectangle packing is NP-hard but maybe not in NP?

In order for a language $L$ to be in NP, there needs to be a way to certify that instance $x$ belongs to $L$. This "way" is a polynomial size witness which can be verified in polynomial time....
16 votes
Accepted

Is every NP-hard problem computable?

No, an $NP$-hard problem need not be computable. The definition is fairly complete: a problem $L$ is $NP$-hard if that problem having a poly-time solution implies every problem in $NP$ has a poly-time ...
  • 29.2k
14 votes
Accepted

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

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case. If, however, $P \neq NP$, ...
  • 1,914
14 votes
Accepted

Is a "local" version of 3-SAT NP-hard?

$(3,k)\text{-LSAT}$ is in P for all $k$. As you have indicated, locality is a big obstruction to NP-completeness. Here is a polynomial algorithm. Input: $\phi\in (3,k)\text{-LSAT}$, $\phi=c_1\wedge ...
  • 35.5k
14 votes

Is the following problem NP-hard? (or have you seen it before?)

What you are describing is a planning and scheduling problem. Kautz and Selman pioneered the use of Boolean satisfiability and SAT solvers to attack such problems in the early 1990's. SATPLAN, ...
  • 7,873
13 votes
Accepted

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

Your intuition about "relative hardness" is correct, the underlying mathematics is why III. is true. However your justification about I. is a little off (not wrong, but the reasoning is possibly not ...
13 votes
Accepted

Spatial embedding of graph

Your parameter is known as sphericity, first defined by Maehara, Space graphs and sphericity. Maehara showed that every graph has such an embedding. Given a graph $G = (V,E)$, embed $x \in V$ into the ...
12 votes

Is every NP-hard problem computable?

Nope. NP-Hard means it is as hard, or harder, than the hardest NP-problems. Intuitively, being uncomputable will make it a lot more difficult than NP. Wikipedia: There are decision problems that ...
12 votes

Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?

Actually, your version is correct and Wikipedia's is wrong! (Except that it has a tiny disclaimer at the bottom.) If $\mathrm{P}=\mathrm{NP}$, Wikipedia claims that every problem in $\mathrm{P}$ is $\...
11 votes
Accepted

Are regex crosswords NP-hard?

The problem is NP-hard. We show this by reducing vertex cover: Given a graph $G=(V,E)$ and a threshold $k$, is there a subset $V' \subseteq V$ of cardinality at most $k$, so that each edge in $E$ ...
  • 6,539
11 votes
Accepted

Is weighted XOR-SAT NP-hard?

A classical result of Berlekamp, McEliece, and van Tilborg shows that the following problem, maximum likelihood decoding, is NP-complete: given a matrix $A$ and a vector $b$ over $\mathbb{F}_2$, and ...
11 votes
Accepted

NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round)

This is a sketch of a reduction from MONOTONE CUBIC PLANAR 1-3 SAT : Definition [1-3 SAT problem]: Input: A 3-CNF formula $\varphi = C_1 \land C_2 \land ... \land C_m$, in which every clause $C_j$ ...
  • 12.3k
11 votes
Accepted

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

A problem $P$ is NP-complete if: $P$ is NP-hard and $P \in \textbf{NP}$. The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). ...
  • 4,909
11 votes

A problem in NP but not NP-complete?

As written, the question is a bit trivial: if NP = NP-complete, then since P $\subseteq$ NP we get P=NP since every problem in P would be NP-complete. I suspect what's meant, though, is the following:...
10 votes

Is every NP-hard problem computable?

For completeness, let us prove the following theorem: There exists an uncomputable language which is not NP-hard if and only if P$\neq$NP. If P=NP then any non-trivial language (one which differs ...
10 votes

Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?

By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no. However, its possible to think instead of solving the ...
  • 10.9k
9 votes
Accepted

Typical NP-complete/hard problems in machine learning

Many theoretical problems in ML are NP-hard. I think the famous AlphaGo is trying to solve a NP-hard problem. Contextual bandit problem and its combinatorial variants are np-hard. In social network ...
  • 206
9 votes
Accepted

What are the hardest problems that are in P if and only if P=NP?

Well, here is a trivial example of a problem. Inputs: a program P, an input x Desired output: if P=NP, output "sweet!", else if P halts on x output "halts", else output "doesn't halt" If P=NP, then ...
  • 145k
9 votes

What is inapproximability of NP-hard problems?

Optimization problems come in two flavors: minimization and maximization. For definiteness, in this answer we consider minimization problems; for maximization problems the situation is completely ...
9 votes
Accepted

Selling blocks of time slots

Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose both $x_i$ and $\overline{x_i}$ appear in the formula for at most $k_i$ times respectively. We design a colored ...
  • 1,163
9 votes
Accepted

NP-completeness of solving quadratic equations over $\mathbb{Z}_2$

You can express the constraint $x \lor y = z$ (where $\lor$ is the OR operator) as the equation $(1-x)(1-y) = (1-z)$, that is, $xy+x+y+z=0$. Using this primitive you can express SAT, showing that your ...
9 votes
Accepted

Is 3-colouring NP-hard for 5-colourable graphs?

Yes, and this holds even for structured graphs. Indeed, every planar graph is 5-colorable (in fact even 4-colorable by the Four color theorem), but it is NP-complete to decide if a planar graph can be ...
  • 22.1k
8 votes
Accepted

The buckets of water problem

The problem is NP-hard, by reduction from SUBSET-SUM. Given a multiset of numbers $x_1,\ldots,x_n$ and a target $T$, consider $n$ buckets with capacity $C=x_1+\cdots+x_n$, initially filled with $x_1,\...
8 votes
Accepted

Richard Karp's 21 NP-Hard problems, the meaning of his research?

The short way to say it is that these problems are $\mathcal{NP}$-complete. Of course this only has meaning to those who understand what $\mathcal{NP}$-complete means. Not only does this say these ...
8 votes
Accepted

Can all NP-hard problems be reduced to one another?

The answer to your question is no. Take for example the $SAT$ problem and Halting problem. Both are NP- Hard but second can't be reduced to first.
8 votes
Accepted

Why is Knapsack and ILP NP-complete

As discussed in the comments, this question hinges around subtleties of the definitions. NP is a set of decision problems (problems with yes/no answers), so any problem such as "Find the shortest XXX" ...

Only top scored, non community-wiki answers of a minimum length are eligible