A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Hot answers tagged

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

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

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


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.


9

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


5

Suppose I have a problem $A$, which is in NP. Suppose there is another problem $B$ in NP, can I reduce $A$ to $B$? Maybe, maybe not. It depends on what $A$ and $B$ are. I suggest you revise the concept of NP-completeness and bear in mind that every problem in P is also in NP. These will help you understand the situation better and I think ...


5

The authors claim that it is easy to show that the problem lies in NP. To prove this claim, take a sequence of swaps that leads to a state as a witness that the state is reachable. Given such a sequence of polynomial size, we can verify in polynomial time that the state is indeed reachable by performing the swaps. What remains to be shown is that there is ...


5

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


5

Add $n$ empty sets, and choose $K = n + 1$. Every solution for the original problem is (without loss of generality) of size between $1$ to $n$, so using the empty sets you can complete it to a solution of size exactly $K$. If you're determined to have your collection duplicate-free, add $n$ new elements $y_1,\ldots,y_n$, and the following sets: $$ \{y_1\},\{...


5

As shown in the previous answer, this problem can be modeled as a scheduling problem with release and due dates. However, Schrage's heuristic works only for the case $p_j=1$ (all processing times are $1$) or when release and due dates agree (i.e. there is an order such that $r_1\leq\cdots\leq r_n$ and $d_1\leq\cdots\leq d_n$). For the case $p_j=p$ ...


5

I suppose an analogous question can also be asked for P and NP. If a problem is in NP, then can every problem in P be reduced in polynomial time to it? No. There is a stupidly simple argument here: the empty language (i.e., a problem with no yes-instances) is in NP, but no problem in P can be reduced to it. Does there exist a problem that is hard to ...


5

The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the budgeted dominating set problem. The problem or its connected variant is studied at least by Lamprou, Sigalis and Zissimopoulos [1] and Khuller, Purohit and Sarpatwar [2]. It also appears in the recent survey of Narayanaswamy and Vijayaragunathan [3]...


4

Edit: See my answer to the same question on math stackexchange here. I've copy and pasted the answer again for ease of use. There has been a recent line of work investigating algorithms for submodular optimization problems when the objective may take negative values. So far, the non-negativity that we can handle is when the submodular objective decomposes ...


4

This Medium post lists the latest (not a full list of course) studies in the combinatorial optimization domain. All three papers use Deep Reinforcement Learning, which does not need any training set but learns completely from its own experience. I have been working on the first paper for some time and inference time is on milliseconds level. According to ...


4

So you have found out $X \in \mathbf{NP}$. Unfortunately, as Juho hints at in their answer, there is no "list" you can systematically go over to try and investigate $X$ further. This is mainly because separation results in complexity theory are (yet) few and far between, so most of the things you may try will not explicitly fail; you'll only be unsuccessful. ...


4

The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem). It is almost universally the case that a reduction is easier than a direct proof. Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners. There are lots and lots of problems known to be NP-complete; ...


4

Hartmanis et al proved that there are sparse set in $PSPACE\backslash NP$ iff $EXPSPACE \neq NEXPTIME$ and it is highly believed they are correct. This sparse set is not in NP and is not NP-hard because it is sparse. Sparse language: In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity ...


4

The restriction $m < 2n$ does not help to solve the problem in polynomial time. Note that any 3-dimensional matching instance can be polynomially reduced into an instance with $m < 2n$ by adding $m$ elements to the sets $X$, $Y$ and $Z$ and $m$ hyperedges to connect these new elements. The resulting instance has $n' = n + m$ and $m' = 2m$, so $m' < ...


3

A maximal clique and a maximum clique are in general different. A set of vertices $S$ is a maximal clique if $S$ is a clique and you cannot add any vertex to $S$ such that the resulting set would form a clique. The set $S$ forms a maximum clique when there is no other set of vertices that forms a clique that is larger than $S$. You mention bipartite graphs, ...


3

Any language $L$ in NP is decided by some nondeterministic Turing machine $M$. By Cook–Levin, the problem "Does $M$ accept input $x$?" can be decided by constructing a Boolean formula $\varphi_{M,x}$ that is satisfiable if, and only if, $M$ accepts $x$. Hence $L$ reduces to SAT, so SAT is NP-hard.


3

Here is a translation of the answer how to prove 4-SAT CNF is NP-complete to the current situation. Suppose an instance of 4-SAT over variables $x_1,x_2,\cdots, x_m$ is given as a boolean formula $$f=c_1\land c_2\land \cdots\land c_m,$$ where $c_i$ is a disjunction that has exactly 4 literals for all $i$. Introduce a new variable $s$. Suppose $c_i=w\lor x \...


3

It depends, you should try to do whatever the problem smells like. You will need experience to get a good hunch. It's also not uncommon to try to do both. You might start by trying to come up with a polynomial time algorithm. Getting stuck? Why is that? Could you simulate that in an NP-hardness proof? Or you might start by building an NP-hardness proof ...


3

It seems that you're trying to prove that $\#\mathrm{3SAT}$ is in $\mathrm{NP}$. Since $\#\mathrm{3SAT}$ is $\mathrm{\#P}$-complete, and $\mathrm{\#P}$ seems to be harder than anything in the polynomial hierarchy, it's very unlikely that $\#\mathrm{3SAT}\in\mathrm{NP}$. The error in your attempted proof is that your certificate doesn't have polynomial ...


3

The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this? First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has ...


3

All NP-complete problems are "equally hard", in the sense that if one of them is in P, then all of them are in P. Similarly, if one NP-complete problem can be solved in quasipolynomial time (that is, time $e^{O(\log^C n)}$ for some constant $C$) then all of them can be solved in quasipolynomial time. Some NP-hard problems are harder than others, but all of ...


3

Your first problem is a classical NP-hard problem known as maximum coverage. The greedy algorithm gives a $1-1/e$ approximation, and this is tight (assuming P≠NP). Your second problem is a special case of set cover. Indeed, take any instance of set cover, and add to it the set $S$ itself. If the optimal solution for the set cover instance is $M$, then the ...


3

Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here) That's not odd at all: it's because no such proof exists. Anything that can ...


3

It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset $N'$ is at least $B$ (which implies that it must actually be exactly $B$) if and only if the corresponding subset sum instance has answer "yes".


3

Let $S, k$ be a given instance of the subset sums problem. The goal is to build an equivalent instance of your problem (let us call it the pens arrangement problem). In the subsetsums problem, we are looking for a subset of the given set that sums up to $k$. So it is intuitive to set $G$ to $k$ and set the lengths of the pens to be the numbers in the given ...


3

Very simple: We can sort an array without checking every possible permutation. (Many times we don’t check any permutation of the array, we just re-arrange the order of items so we can guarantee the array is sorted, without ever checking it. )


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