What makes a problem computationally NP?

[2sin54]

As the title says, what makes a decision problem NP complex? Is it application of the definition (as in: solvable in polynomial time by a non-deterministic Turing machine)? Also, if P does not equal NP, does it mean that NP problems can only be solved in O(exp(n)) time/steps?

 

[fresh_42]

As the title says, what makes a decision problem NP complex? Is it application of the definition (as in: solvable in polynomial time by a non-deterministic Turing machine)?

Yes. If you can solve a problem in polynomial time only if a random tape is available, then it's in NP.

Also, if P does not equal NP, does it mean that NP problems can only be solved ...

deterministic

... in O(exp(n)) time/steps?

Yes, except it is already in P. It does not mean that a single instance of a problem couldn't be solved in P, only the problem in general can't.

 

[Jarvis323]

As the title says, what makes a decision problem NP complex? Is it application of the definition (as in: solvable in polynomial time by a non-deterministic Turing machine)? Also, if P does not equal NP, does it mean that NP problems can only be solved in O(exp(n)) time/steps?

NP is the set of decision problems where the yes answers can be verified in polynomial time. P is a subset of NP. Note that every problem with time complexity less than polynomial is also in P.

NP may contain more than just P. This is the case if there are problems whose solutions can be verified in polynomial time, yet cannot be solved in polynomial time (that is finding the solution is more difficult than checking that it is correct ).

The answer to the first question you asked is yes, but I think it's better to think of it the way I explained it (yes answers can be verified in polynomial time). The answer to the second is no, like I said, P is subset of NP. NP-Complete problems are those that are in NP and NP-Hard (as hard as the hardest problems in NP). Those problems, if P is not equal to NP, are not solvable in Polynomial time.

 

[2sin54]

The answer to the second is no, like I said, P is subset of NP. NP-Complete problems are those that are in NP and NP-Hard (as hard as the hardest problems in NP). Those problems, if P is not equal to NP, are not solvable in Polynomial time.

But I did not claim that if P equals NP, then NP problems are solvable in Polynomial time. O(exp(n)) is exponential time and I was wondering if (given P is not equal to NP) the NP problems are only solvable in exp(n) time.

 

[Jarvis323]

But I did not claim that if P equals NP, then NP problems are solvable in Polynomial time.

If P and NP are the same set, then of course all problems in NP are in P.

O(exp(n)) is exponential time and I was wondering if (given P is not equal to NP) the NP problems are only solvable in exp(n) time.

NP is a superset of all problems easily verified, this includes O(1) problems, O(n) problems etc. If NP is not P, then it just means that P is strictly a subset of NP, not all of NP (it would mean there are at least some NP problems that are not in P).

 

[2sin54]

NP is a superset of all problems easily verified, this includes O(1) problems, O(n) problems etc. If NP is not P, then it just means that P is strictly a subset of NP, not all of NP (it would mean there are at least some NP problems that are not in P).

What about if P is not equal to NP? Would the problems that are in NP but not in P be of exponential complexity?

 

[Jarvis323]

What about if P is not equal to NP? Would the problems that are in NP but not in P be of exponential complexity?

This article should answer the question pretty well. If P is not NP, then there are problems in-between P and NP-Complete.
https://en.wikipedia.org/wiki/NP-intermediate

 

[stevendaryl]

What about if P is not equal to NP? Would the problems that are in NP but not in P be of exponential complexity?

Well, NP is its own complexity classification.

Here's the way I understand it:

If a problem is in P, that means that you can find a solution in polynomial time.
If a problem is in NP but not in P, that means that you can check whether a solution is actually a solution in polynomial time, but it would take you longer than polynomial to find it.

The distinction between checking a solution and finding one is illustrated by the 4-color problem. You have some map of countries, and you want to pick colors from the choices Red, Yellow, Blue, Green, so that no two countries that share an edge have the same color. Coming up with a choice of colors might be very difficult: You might have to try every possible combination, and that's $4^N$ possibilities, where $N$ is the number of countries. So finding a solution might be exponential. But if somebody just handed you a colored map, you could check that no countries with a shared edge are the same color in at worst $N^2$ steps (go through every possible pair of countries, see if they share a border, and then check if they are the same color).

That might not be an example of an NP problem, though, because there might be some clever way to cut down the number of possibilities, but it shows you the idea.

 

[2sin54]

That might not be an example of an NP problem, though, because there might be some clever way to cut down the number of possibilities, but it shows you the idea.

Thank you for your answer. So is P - NP distinction unrelated to the algorithmic complexity of a problem? It should be though, shouldn't it? Because a problem in P is solvable in polynomial time (think O(t^N)). But what about NP, if it is not equal to P?

 

[fresh_42]

Thank you for your answer. So is P - NP distinction unrelated to the algorithmic complexity of a problem? It should be though, shouldn't it?

Why that? A distinction means you have a problem, which is in NP but not in P. For being in NP you'll need an algorithm, for not being in P you'll need a proof. But be aware that the problem is unsolved for decades now, and it is notoriously hard to prove non existence. We basically have to show, that it's not our incapability, but hard by nature.

Because a problem in P is solvable in polynomial time (think O(t^N)). But what about NP, if it is not equal to P?

A problem in NP means it can be solved in exponential time and verified in polynomial. A famous example is whether Boolean expressions are true for some setting of the variables or not. To test all possibilities is exponential in time, and to check whether a setting yields true or false is polynomial. We do not know a polynomial time algorithm to find a general solution, yet. So a proof NP = P is easier than a proof P $\subsetneq$ NP, because for the former we needed only a smart algorithm to solve this Boolean problem. However, one cannot prove both. Until now, nobody has found a smart algorithm, and nobody could prove, that it's impossible.

 

[QuantumQuest]

I just want to add some things to all the well-said things so far.

As the title says, what makes a decision problem NP complex? Is it application of the definition (as in: solvable in polynomial time by a non-deterministic Turing machine)?

A time-bounded TM is one that, given an input of length n, always halts in $T(n)$ moves and it is said to be $T(n)$ time bounded. The TM can be multi-tape and sometimes it can be deterministic. Now, if a DTM is $T(n)$ time bounded for some polynomial $T(n)$ then we say that this TM is polynomial time bounded. Then, its language $L(m)$ is said to be in the class P - it's the same thing to talk about the class P of problems or languages. The class NP is problems that can be solved by a TM that is non-deterministic but has a time bound along each branch. Now, as already noted, if for a NTM its time bound i.e. its running time (= maximum number of steps taken along any branch) is polynomial then this NTM is said to be polynomial - time bounded and its language is said to be in NP.

Also, if P does not equal NP, does it mean that NP problems can only be solved in O(exp(n)) time/steps?

Regarding the P = NP open question, there are various ways to address it. One such way is through NP - complete problems. An NP - complete problem (defined formally via poly-time reductions) has the property that it is in NP and if it is in P, then every problem in NP is also in P. It turns out that almost every problem that is known to be in NP but it is not known to be in P, is NP - complete. There is only one well known exception: graph isomorphism. Also, there are thousands of problems that are in NP but appear not to be in P. Unfortunately, no proof that they are not really in P.

Now, regarding problem reduction, an example of a problem definitely in NP is the Knapsack Problem. A dynamic-programming algorithm which maintains a table of all the differences that can be achieved by partitioning the first i integers, could seem to solve the problem in polynomial time but there is the subtlety of measuring the input size. But if we redefine the problem by representing integers in unary - that is pseudo-knapsack, then this problem is in P.