Why do people say that some problem is hard when they do not actually prove it?

86 Views Asked by At

I have read many times in different papers something like the following (I do not remember the exact words though):

  • "The problem is nonlinear non-convex programming problem which is hard to solve."
  • "The problem is an integer programming problem which is NP-hard."
  • "The problem involves binary variables which necessitates exhaustive search."
  • ...

Why do people say these kind of words in their work? Maybe because they do not know if these problems are indeed hard?

Is it even true to say that, for example, it is a nonlinear programming problem then it is hard?

Here is an example which involves binary variables, integer programming and is easy to solve. (It is a knapsack problem where the values of each item are all equal.)

\begin{align} &\text{maximize}\quad \sum_{i=1}^{n}x_i\\ &\text{subject to}\quad \sum_{i=1}^{n}w_ix_i\leqslant W\\ &\quad \quad\quad\quad\quad\; x_{i}\in\{0,1\}\text{ for all } i \in\{1,\ldots,n\}. \end{align}

If I am not mistaken, an $O(n\log n)$ solution is the following. enter image description here

1

There are 1 best solutions below

1
On BEST ANSWER
  • "The problem is nonlinear non-convex programming problem which is hard to solve."

"Hard" in the context of the time and space requirements of an algorithm or problem typically means "in exponential time (or space)".

  • "The problem is an integer programming problem which is NP-hard."

This means the problem is supposed to have the same complexity like a problem from NP.

  • "The problem involves binary variables which necessitates exhaustive search."

Uhm, yes.