# Tag Info

Accepted

### Hardness of a problem which is the sum of two NP-Hard problems

Nothing. Lower bound: Suppose $h(x) = -f(x)$. Then $\sum_x g(x) = 0$, which is trivial to compute. If $\sum_x f(x)$ is NP-hard to compute, then $\sum_x h(x)$ will be too, but $\sum_x g(x)$ will be ...
• 162k
Accepted

### Is the following problem NP-hard? (or have you seen it before?)

This problem (more formally its decision version) is NP-complete. NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be ...
• 296
Accepted

### Is detecting easy instances of NP-hard problems easy?

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 ...
• 162k
Accepted

### Why rectangle packing is NP-hard but maybe not in NP?

In order for a language $L$ to be in NP, there needs to be a way to certify that instance $x$ belongs to $L$. This "way" is a polynomial size witness which can be verified in polynomial time....
• 278k
Accepted

### Is every NP-hard problem computable?

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 ...
• 29.8k
Accepted

### Do any decision problems exist outside NP and NP-Hard?

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$, ...
• 3,183
Accepted

• 81.9k

### A problem in NP but not NP-complete?

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:...
• 2,818

### What is inapproximability of NP-hard problems?

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 ...
• 278k
Accepted

### Is "Reachable Object" really an NP-complete problem?

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). ...
• 5,027
Accepted

### What are the hardest problems that are in P if and only if P=NP?

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 ...
• 162k

### Is every NP-hard problem computable?

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 ...
• 278k

### Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?

By definition, if you were to find a polynomial time algorithm for an NP-hard (or NP-complete) problem, then $P=NP$. So, short answer is - no. However, its possible to think instead of solving the ...
• 11.6k
Accepted

### Can a graph problem remain NP-hard when restricted to cycle graphs?

Assuming the problem instance is defined solely by the cycle itself (no labels or weights on the nodes, etc., no other inputs to the algorithm), then no, you should not expect any such problem to be ...
• 162k
Accepted

### Typical NP-complete/hard problems in machine learning

Many theoretical problems in ML are NP-hard. I think the famous AlphaGo is trying to solve a NP-hard problem. Contextual bandit problem and its combinatorial variants are np-hard. In social network ...
• 206
Accepted

### Selling blocks of time slots

Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose both $x_i$ and $\overline{x_i}$ appear in the formula for at most $k_i$ times respectively. We design a colored ...
• 1,183
Accepted

### NP-completeness of solving quadratic equations over $\mathbb{Z}_2$

You can express the constraint $x \lor y = z$ (where $\lor$ is the OR operator) as the equation $(1-x)(1-y) = (1-z)$, that is, $xy+x+y+z=0$. Using this primitive you can express SAT, showing that your ...
• 278k
Accepted

### Relation between Undecidable problems and NP-Hard

I believe that this answer by Yuval Filmus all the questions you have asked. If P=NP then any non-trivial set is NP-hard (other than the empty set and the complete set), so assume P$\neq$NP. If $A$ ...
• 175
Accepted

### Is 3-colouring NP-hard for 5-colourable graphs?

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 ...
• 22.6k
Accepted

### What is a witness string? I unable to understand the concept

To give a concrete example, imagine you have a box of 4-digit combination padlocks. All those padlocks are closed, but some of them have a defect and no code can open them. Given a padlock, you want ...
• 15.8k
Accepted

### Why is Knapsack and ILP NP-complete

As discussed in the comments, this question hinges around subtleties of the definitions. NP is a set of decision problems (problems with yes/no answers), so any problem such as "Find the shortest XXX" ...
• 81.9k

### Are there any optimization problems in P whose decision version is hard?

No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves ...
• 81.9k

### What will happen to NP-Hard problems if P=NP

No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in ...
• 350
Accepted

### Proofs of reduction of any hard problem

The first "approach" is the definition of a polynomial time many-one reduction. This is the type of reductions used for defining NP-hardness: a problem $B$ is NP-hard if for every problem $A$...
• 278k