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$ – NimaKimi Dec 30 '19 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 '19 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.