Problem complexity


Computational complexity

P

NP

Unsolved problem: Is P = NP ?

NP-Complete

co-NP

Unsolved problem: Is NP = Co-NP ?

co-NP-Complete

NP-Hard

NP-Easy

Space complexity

ie, with respect to memory.

Space, unlike time, can be reused.

PSPACE

Amount of space required is polynomial in the input size.

In polynomial time, an algorithm can only use polynomial amount of space. ie,

P โŠ† PSPACE

There is a PSPACE solution to 3-SAT problem. Consequently,

NP โŠ† PSPACE

Not proven that P โ‰  PSPACE though that seems likely.

PSPACE Complete

More

NC

Time complexity

Polylgorithmic time

Time is in O(logแตn) which is same as O((log n)แต)

Related stuff

Reducing a problem to another

Even when it is possible to reduce a problem X another problem Y in polynomial time, it may not be possible to reduce Y back to X.

For example, any computation problem can be converted to the halting problem (where the Turing halts for the output), but the halting problem cannot be converted to the computation problem (for the cases where the Turing machine doesn't halt). (A discussion)

Complement of a problem

Certificate of complexity

A solution path in within a verification process.

References

Doubts