Hot answers tagged

77

Worst-case Hardness of NP-complete problems is not sufficient for cryptography. Even if NP-complete problems are hard in the worst-case ($P \ne NP$), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using ...


49

There have been. One such example is McEliece cryptosystem which is based on hardness of decoding a linear code. A second example is NTRUEncrypt which is based on the shortest vector problem which I believe is known to be NP-Hard. Another is Merkle-Hellman knapsack cryptosystem which has been broken. Note: I have no clue if the first two are broken/how ...


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


27

As you said, there is no decision to make, so new complexity classes and new types of reductions are needed to arrive at a suitable definition of NP-hardness for optimization-problems. One way of doing this is to have two new classes NPO and PO that contain optimizations problems and they mimic of course the classes NP and P for decision problems. New ...


25

I can think of four major hurdles which are not entirely independent: NP-hardness only gives you information about complexity in the limit. For many NP-complete problems, algorithms exist that solve all instances of interest (in a certain scenario) reasonably fast. In other words, for any fixed problem size (e.g. a given "key"), the problem is not ...


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


19

Usually what's shown is the NP-hardness of a "Gap" version of the problem. For example, suppose that you want to show that it's hard to approximate SET COVER to within a factor of 2. You define the following "promise" instance of SET COVER that we'll call 2-GAP-SET-COVER: Fix some number $\ell$. 2-GAP-SET-COVER consists of all instances of set cover where ...


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


16

There appears to be some considerable confusion in this community regarding this question. I'll give a detailed answer in the hope of clearing up the water and illuminating the relationship between computability and NP-hardness. First, I believe that being clear and explicit about the various definitions involved will resolve a lot of the confusion. A ...


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


14

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


13

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


13

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


12

The differentiability requirement doesn't change the nature of the problem: requiring $\mathcal{C}^0$ (continuity) or $\mathcal{C}^{\infty}$ (infinite differentiability) gives the same lower bound for the length and the same order of points, and is equivalent to solving the traveling salesman problem. If you have a solution to the TSP, you have a $\mathcal{...


12

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

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

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

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

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

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


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


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

Reduce from NP-complete SET-COVER instead. Let $S_1,\dots,S_m \subseteq\{1,\dots,n\}$ with $k\in\mathbb{N}$ an instance of set cover. Define an instance $(V,E,k')$ of DGD like this: $V= \{s_1,\dots,s_m,o_1,\dots,o_m,e_1,\dots,e_n,o\}$ $E= \{(s_i,o_i) \mid i = 1,\dots,n \} \cup \{(s_i,e_j)\mid j \in S_i\} \cup\{(e_j,o)\mid j=1,\dots,n\}$ $k' = m + k$ It is ...


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

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


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