Hot answers tagged

38

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 easy to compute. Upper bound: Suppose $h(x) = f(x)$. Then $\sum_x g(x) = 2 \sum_x f(x)$, which is as hard as computing $\sum_x f(x)$, which is assumed to be NP-...


22

${\rm D{\small OMINOSA}}$ is NP-hard Playing the game is an optimization problem; finding a valid domino tiling such that it covers all the squares. The decision version of this problem is: Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles? Obviously, the optimization problem, the problem of actually finding a ...


18

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 NP hard. In the JSP, we have $n$ jobs $J_1, J_2, ..., J_n$. Within each job there is a set of operations $O_1, O_2, ..., O_n$ which need to be processed in a ...


17

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 input you give it, all it does is just print $S$. This answer counts as a deterministic polynomial-time algorithm that solves this particular instance $I$. ...


16

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 solution (that is, a reduction to $L$ exists for every problem in $NP$.). Uncomputable problems are then vacuously hard: suppose we could solve one in ...


14

$(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 c_2\cdots \wedge c_m$, where $c_i$ is the $i$-th clause. Output: true if $\phi$ becomes 1 under some assignment of all variables. Procedure: Construct set $B_i$...


14

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, STRIPS, and PDDL are good search terms for further research. There seem to be several planner implementations that take world descriptions written in STRIPS and ...


13

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 accurate). It might help to think about reductions in these terms (everything I'll talk about here will be polynomial time, so I will leave that out just so I ...


12

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$, then there are languages which are neither in NP nor NP-hard. For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this ...


12

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 are NP-hard but not NP-complete, for example the halting problem. Everyone knows that is not computable


12

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 $\mathrm{NP}$-complete. However, this is not true: in fact, every problem in $\mathrm{P}$ would be $\mathrm{NP}$-complete, except for the trivial languages $\...


11

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$ is incident to at least one node in $V'$? We translate this into a regex crossword with $|E|+1$ columns and $|V|$ rows as follows: All columns, except for the ...


11

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). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction ...


10

You claim that every problem in NP can be reduced to its complement, and this is true for Turing reductions, but (probably) not for many-one reductions. A many-one reduction from $L_1$ to $L_2$ is a polytime function $f$ such that for all $x$, $x \in L_1$ iff $f(x) \in L_2$. If some problem $L$ in coNP were NP-hard, then for any language $M \in NP$ there ...


10

This problem can be solved in polynomial time, using bipartite matching. For a bipartite graph with $n$ vertices on the left, corresponding to the $n$ rows, and $n$ vertices on the right, corresponding to the $n$ columns. Include an edge from $i$ to $j$ if $C(i,j)=1$, i.e., if you're allowed to place a rook in the $(i,j)$ square (in the $i$th row and $j$th ...


10

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$ contains exactly three literals: $C_j = (\ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3})$. Question: Does there exist a satisfying assignment for $\varphi$ such that ...


10

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 from $\emptyset,\{0,1\}^*$) is NP-hard (exercise), and in particular any uncomputable language is NP-hard. Now suppose that P$\neq$NP. Let $T_i$ be some ...


10

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: Suppose there are no NP-intermediate problems; that is, that every problem in NP is either in P or is NP-complete. What does that tell us about P vs. NP? ...


10

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 problems fully, to approximate a solution, or to solve them randomly. There are attempts at attacking from those points of view, but they are not perfect at all. ...


9

Note: This is a continuation and revision of my other answer. Problems with the reduction Recall the decision problem: Is there a perfect tiling covering a given a $(n+1) \times (n+2)$ grid with $n$ unique tiles? So for an $(n+1) \times (n+2)$ grid, we can only use $n$ variables. But: Our reduction requires a lot of unique variables, much more than $\...


9

Every NP-complete program $A$ is co-NP hard under Cook reductions: given a problem $B$ in co-NP, its complement $\overline{B}$ is in NP, so there is a polytime function $f$ such that $f(x) \in A$ iff $x \in \overline{B}$. Therefore the following is a Cook reduction from $B$ to $A$: given $x$, ask whether $f(x) \in A$, and return the opposite. This shows ...


9

You can't simply say: "This is a bin packing problem and therefore NP-hard." Consider the problem of $N$ unit bins and $M$ unit items with the target of maximizing the usage of the bins. Clearly this is also a bin packing problem, but it is not NP-hard. However, you can reduce to the decision variant of your problem from partition: Given a set of items ...


9

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 an integer $w$, determine whether there is a solution to $Ax = b$ with Hamming weight at most $w$. You can reduce this problem to your problem. The system $Ax = ...


9

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 this problem is in P. If P$\ne$NP, then this problem is very hard (it's undecidable). I realize this might not be what you're looking for; if so, perhaps it ...


9

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 analogous. Generally speaking, when we say that a minimization problem $\Pi$ is $c$-hard to approximate, we mean the following: If there is a polynomial time ...


9

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 DAG $G$ whose vertices consists of three parts: "Assignment" vertices $v_i(j)$ and $\bar{v}_i(j)$, $1\leq i\leq n$, $1\leq j\leq k_i$. Color $v_i(j)$ with the ...


9

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 problem is NP-hard. Showing that it is in NP is easier.


9

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 colored in 3 colors.


8

Hint: Take a new variable $x$ and add it to all clauses. This shows that HALF-SAT' is NP-hard, where HALF-SAT' differs from HALF-SAT by strengthening "at least half" to "more than half". HALF-SAT is similar. The $P$-closure of HALF-SAT' (and HALF-SAT) forms the complexity class $PP$.


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