New answers tagged np-hard
1
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 ...
0
If one has access to a polynomial algorithm solving $Z$, then there exists a polynomial algorithm for $Z$. That's the main point of reductions for complexity classes. Problem $X$ is at least as hard as problem $Z$.
Another point to be made here is that the class $NP$ is about worst-case complexity, i.e. language $X$ can be $NP$-hard because some instances ...
2
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 ...
1
Not multiplying by $2Cn/\delta$, does not result in
... Exact Cover having no solution if the optimal DTSP tour has length at least $L+\delta+Cn$.
It in fact would result in a length at least $L+\delta$. This length is not always greater than $L+ Cn$, hence the need to multiply all distances by $2Cn/\delta$, after which one obtains the authors' result : ...
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 ...
1
If $F\in 3SAT$ it means that there is some assignment that satisfies $n$ clauses. It doesn't mean that every assignment satisfies all clauses. This makes the reduction wrong, since there might be an assignment for $F\in 3SAT$ that satisfies fewer than $n$ clauses. The reduction you've proposed would be valid if you started with $Tautology$, but then, that ...
0
Let $G=(V,E)$ be an unweighted graph (think of all the edges as having weight $1$), $n=|V|$, and $\bar{G}$ be the edge-complement of $G$.
Now, $C$ is a vertex cover of $G$ iff $\bar{C} = V \setminus C$ is an independent set of $G$, that is, iff $\bar{C}$ is a clique of $\bar{G}$.
When you combine this with the fact that a clique of size $k$ has $\binom{k}{...
0
Let A be the smallest of the $a_i$. Then there are two choices for the first $c_i$ to pick that cannot obviously be improved: One, find the i such that $a_i = A$ and $b_i$ is as small as possible, then let $c_i = a_i$. Two, pick j such that $a_j = A+1$, $b_j<b_i$, and $b_j$ as small as possible, then let $c_j=b_j$ (this may not be possible). Then remove ...
0
Let $k=1$. Since there exist statements that have multiple very short proofs, there must be some sentence that has a shortest proof longer than its own length. So we already live in the "bad world" you're imagining. Since any short proof can have an irrelevant line introduced without changing anything as long as that line is a tautology, we even live in a ...
0
If you allow arbitrary $e_i$, you are in muddy ground. Are your numbers real? No way to express them finitely, NP-whatever right out the window. Rational? The input size can blow up almost arbitrarily, again nothing relevant to prove.
Note that (for very good reasons) NP-hard and its ilk talk about the worst case complexity of the problem (that is well-...
0
If the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?
This depends on how technically precise you want to be.
The most correct answer is "No". Consider an optimisation problem $OP$ for which the encoded length of the output is superpolynomial in the encoded length of the input. Clearly no algorithm ...
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$ ...
0
Your problem is known as non-preemptive single-machine scheduling with release
times and deadlines, with tasks of identical length, and can be solved efficiently using Schrage's greedy heuristic.
Let us first describe the problem more formally. We are given a sequence of time intervals $[r_i,d_i]$ and a sequence of job lengths $p_i$. We want to schedule ...
Top 50 recent answers are included
