What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we make a distinction about the space-time solvability of such problems. Also, I know that you can make reductions (of polynomial time) between problems, so if you know that a problem belongs to a certain class, then the other problem will also belong to this class. Also, I know that the Simplex algorithm solves problems for linear programming

What I would like to know: I would like to know how to "guess" if a problem belongs to NP Class. Does it have to do with the constraints of the problem, the number of constraints, the "type" of constraints?

An example In this link https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/ we can see an algortihm that solves "Maximum profit by buying and selling a share at most k times" with dynamic programming.

However, what if we increase the constraints. Let's say that we are limited to a net worth (we don't have unlimited money) or we can buy and sell more than one stock at a time but we are limited to the ammount of stocks we can buy or sell in the given time, or there are multiple stocks of various companies we can choose from but we are limited in the total number of stocks we can have.

How can we know what kind of constraints make the problem harder and harder "moving" it from P to NP Class ? What kind of constraints should a problem have to be sure that this problem certain belongs either to P or NP Class ?

  • $\begingroup$ Constraints that make the time-complexity worse than $\mathcal{O}(n)$ for the problem, make it easier to move from $\mathrm{P}$ to $\mathrm{NP}$. The heart of the problem is not only about constraints, you need to analyse the whole problem to determine in which class it belongs. So you can't be sure if a problem belongs to a certain class just by checking the constraints. There are also countable many problems in $\mathrm{P}$, while there are uncountable many problems in the $\mathrm{NP}$ class, which is why most of the problems belong the the $\mathrm{NP}$ class. $\endgroup$
    – NimaJan
    Dec 30, 2019 at 15:51
  • 1
    $\begingroup$ First of all, P is contained in NP. Maybe you mean NP-hard or NP-complete. Also, the last statement of Nima is obviously false. The class NP is countable since there are only countable many decidable problems. $\endgroup$
    – Daniel
    Dec 30, 2019 at 21:13

1 Answer 1

  1. Make sure you use NP correctly. To say something belongs to NP doesn't really say anything, except that a right solution of the problem can be checked fast.

  2. From my experience, it's more about the type of problem than what specific constraints you give it.
    For example Indipendent-Set: Including a vertex at one end of the graph may inpact if you can take a vertex at the other end of the graph. This kind of unforeseeable side-effects makes it impossible to really find an algorithm, because you can't decide anything about your solution because you don't know the implications.

On the contrary is sorting: If you use quicksort, you can pick a pivot and split the elements into 2 parts, the ones lower and the ones higher than the pivot.
This way you already made the problem easier: You only need to sort these 2 parts, and you know which of them belongs to which side of the pivot.

Getting such a handle on a NP-hard problem was not successful yet.

I know that this was pretty vague, in the end you can't generalize your question. Every change to a given problem may generally make it NP-hard, you need to look individually.

To prove that something is NP-hard, you can try to reduce an known NP-hard problem to it. This is how it's done with most of them.

An example for your question would also be:
The Maximum-Cut problem is NP-hard, but if you only ask if there exists a cut of size |E|, then it becomes easy, because it is equivalent to asking if the graph is bipartite


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.