New answers tagged np-hard
2
I will assume that $g(G, v)$ computes a valid vertex cover, so it can never report a more optimal solution, and does so in polynomial time.
We know that vertex cover is NP-hard to approximate within a factor below 1.36: http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf. Since $g(G, v)$ reports a solution at most 5 more than optimal, ...
2
Nice question! Let us call this problem the minimum label-covering problem.
We will reduce the hitting set problem, a well-known $\mathsf{NP}$-hard problem to the minimum label-covering problem, thus proving it is also $\mathsf{NP}$-hard. Our strategy is simply translating "intersecting the $i$-th set" in the hitting set problem to "labelled with the $i$-...
0
A clause in 3-CNF can be converted to k-CNF by adding extra padding:
(l1 V l2 V l3) can be converted to (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y')
Keep adding this extra padding until each clause contains k literals.
Same way, a k-CNF clause can be broken until each clause contains 3 literals.
(l1 V l2 V l3 V l4) can be broken into (l1 V l2 V y) ∧ (l3 V ...
-1
The answer is (trivially) yes. Any non-decidable language provides a decision problem that is harder than anything in NP.
1
As pointed out by Antti Röyskö the solution $\mathbf{x} = 0$ always maximizes the objective function since $\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$ corresponds to the number of constraints $\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0$ which are satsificed, and $\mathbf{x}$ satifies all constraints.
However, the problem ...
1
Your understanding is correct, but the takeaway here is that assuming the contradictions implies that anything can be true. Perhaps reading up on some logic rules might help, the important rule here is that $\bot$ (false) implies everything. Here is a little proof of the problem just for fun:
We know that both 3-SAT and Set Cover are NP-Complete problems.
...
2
As in the comment, consider the collection of problems $N$-SAT (Is $\phi$, a logical formula in $N$-CNF, satisfiable?). Or $N$-coloring of graphs, for $N \ge 3$ (Can the graph be colored with $N$ colors?). Many NP-complete problems have some parameter (Is there a clique of size $k$ in the graph? Has the digraph a feedback vertex set of size $k$?).
0
For every integer k, take the travelling salesman problem with n > 1 cities where n is a power of k. (Picked the problem that way because all the instances are distinct, so we can say with good conscience that these are distinct problems).
2
You are confusing NP and NP-hard in a couple places. For example, let $A$ be the problem of deciding ATL*, which is 2EXPTIME-complete. $A$ is NP-hard and polynomial-time many-one reduces to its complement, but is neither in NP nor in co-NP by the time hierarchy theorem.
Recall that an NP-complete problem is one that is in NP and is NP-hard. For every NP-...
Top 50 recent answers are included
