Hot answers tagged

33

By the nondeterministic version of the time-hierarchy theorem, we have $\mathsf{NP} \subsetneq \mathsf{NEXP}$, where $\mathsf{NEXP}$ is the class of problems solvable in non-deterministic exponential-time. Thus it suffices to consider any problem which is $\mathsf{NP}$-hard and in $\mathsf{NEXP}$, but not in $\mathsf{NP}$. For instance, we may consider any $\...


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

Informally: In DNF, you can pick any clause to be true, to make the formula true. This means that a DNF that is equivalent to a certain CNF, is basically an enumeration of all the solutions to boolean sat on the CNF. Note, there can be an exponential number of solutions. Since solving boolean sat for CNF for a single solution is NP-complete, converting to ...


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


15

Public-key cryptography as we know it today is built on one-way trapdoor permutations, and the trapdoor is essential. For a protocol to be publicly secure, you need a key available to anyone, and a way to encrypt a message using this key. Obviously, once encrypted, it should be hard to recover the original message knowing only its cipher and the public key :...


15

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

It looks like you are trying to compute a hypergraph transversal of size $k$. That is, $\{T_1,\dots,T_m\}$ is your hypergraph, and $S$ is your transversal. A standard translation is to express the clauses as you have, and then translate the length restriction into a cardinality constraint. So use your existing encoding, i.e., $\bigwedge_{1 \le j \le m} \...


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


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

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

You actually already have a reduction from special to general. By setting $s=0$, you are basically using the general algorithm to solve the special problem. For the other way round (i.e. a reduction from general to special): Suppose you are given a set $S = \{x_1, \dots, x_n\}$ and a number $K$ and you have to determine if there is some subset of $S$ which ...


11

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


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

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


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

No. E.g. the Halting problem is a decision problem which is NP-hard but not in NP and therefore not NP-complete. In normal usage yes, because an NP-complete problem must be in NP and NP is a class of decision problems. But see Decision problems vs “real” problems that aren't yes-or-no.


10

I'm assuming that you're thinking of the Euclidean traveling salesman problem, where $c$ and $v$ are vectors in $\mathbb{Z}^{2n}$, with two coordinates for each city. Let $minTSP(c)$ denote the length of the minimum traveling salesman tour for the cities with coordinates $c$. Then your problem asks whether $$ minTSP(c + v) \ge min TSP(c) + x. $$ But then ...


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

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


9

See the definition of NP completeness. For a problem to be NP-complete, it needs to be in NP and all NP problems need to be reducible to it in polynomial time. Condition 2 alone is what it means to be NP hard. Thus NP complete problems are the intersection of NP problems and NP hard problems. NP $\subseteq$ EXPTIME, thus NP problems can be solved in $2^...


9

First we reduce the task of factorization to finding any factor of $n$ (or showing that it's prime). Once we know how to do this, we divide $n$ by such an factor and repeat the process until all factors are broken down to primes, and this takes $O(\log n)$ steps. Let $k=\lceil\log_2 n\rceil$ the number of bits in $n$. Next, we design a binary ...


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

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

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


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