Skip to main content
38 votes
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 ...
D.W.'s user avatar
  • 162k
18 votes
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 ...
Surpriser's user avatar
  • 296
17 votes
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 ...
D.W.'s user avatar
  • 162k
17 votes
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....
Yuval Filmus's user avatar
16 votes
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 ...
Joey Eremondi's user avatar
14 votes
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$, ...
Arno's user avatar
  • 3,183
14 votes
Accepted

Is a "local" version of 3-SAT NP-hard?

$(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 ...
John L.'s user avatar
  • 39.1k
14 votes

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

What you are describing is a planning and scheduling problem. Kautz and Selman pioneered the use of Boolean satisfiability and SAT solvers to attack such problems in the early 1990's. SATPLAN, ...
Kyle Jones's user avatar
  • 8,101
13 votes
Accepted

Spatial embedding of graph

Your parameter is known as sphericity, first defined by Maehara, Space graphs and sphericity. Maehara showed that every graph has such an embedding. Given a graph $G = (V,E)$, embed $x \in V$ into the ...
Yuval Filmus's user avatar
12 votes

Is every NP-hard problem computable?

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 ...
Destructible Lemon's user avatar
12 votes

Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?

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 $\...
David Richerby's user avatar
12 votes

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:...
Noah Schweber's user avatar
11 votes

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 ...
Yuval Filmus's user avatar
11 votes
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). ...
dkaeae's user avatar
  • 5,027
10 votes
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 ...
D.W.'s user avatar
  • 162k
10 votes

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 ...
Yuval Filmus's user avatar
10 votes

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 ...
nir shahar's user avatar
  • 11.6k
10 votes
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 ...
D.W.'s user avatar
  • 162k
9 votes
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 ...
HenryZhao's user avatar
  • 206
9 votes
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 ...
Wei Zhan's user avatar
  • 1,183
9 votes
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 ...
Yuval Filmus's user avatar
9 votes
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$ ...
Alex Smart's user avatar
9 votes
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 ...
Juho's user avatar
  • 22.6k
9 votes
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 ...
Nathaniel's user avatar
  • 15.8k
8 votes
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" ...
David Richerby's user avatar
8 votes

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 ...
David Richerby's user avatar
8 votes

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 ...
HackerBoss's user avatar
8 votes
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$...
Yuval Filmus's user avatar
7 votes
Accepted

Traveling Salesman Problem with Neural Network

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 ...
tahsin kose's user avatar

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