Computational complexity
P
- Solvable in polynomial time.
- Verifiable in polynomial time.
- Tractable problems
- Mentioned in Cobham's
thesis (although not under this name).
- A problem is in P, then its complement is also in P.
NP
- No polynomial time solution
- NP stands for 'Non-deterministic Polynomial acceptable problems' (Source)
- Verifiable in polynomial time.
- Example: 3-SAT
Unsolved problem: Is P = NP ?
NP-Complete
Like 'Hardest problems in NP' (but still got to be NP, unlike in
the case of NP-Hard)
All NP problems can be reduced to an NP-C problem in polynomial
time.
If a polynomial time solution was found to an NP-C problem, we
can conclude that P = NP
Example: Circuit satisfiability
NP-C โ NP
co-NP
- A problem is in co-NP if its complement is in NP.
- Therefore, the complement of every NP problem is co-NP.
Unsolved problem: Is NP = Co-NP ?
co-NP-Complete
- A problem is in co-NP-C if its complement is in NP-C.
- Therefore, the complement of every NP-C problem is co-NP-C.
NP-Hard
- Like 'at least as hard as the hardest problems in
NP'.
- May not be even be NP.
- May not be even be decidable.
- Example: Subset sum problem
NP-Easy
- Like 'at most as hard as NP', but not necessarily in NP.
Space complexity
ie, with respect to memory.
Space, unlike time, can be reused.
- DSPACE
- NSPACE: Non-deterministic counterpart of DSPACE
PSPACE
- Requires only polynomial memory space
- A problem is in PSPACE, then its complement is also in 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
- Any problem in PSPACE can be converted into this in polynomial
time.
- Considered the hardest problems in PSPACE as a solution to a PSPACE
Complete problem can be used to solve any PSPACE problem.
- Suspected to be outside P and NP, but not proven.
More
NC
Time complexity
Polylgorithmic time
Time is in O(logแตn) which is same as O((log n)แต)
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
- Can a NP-C problem be reduced to an NP
- DEXP TIME
- EXPTIME-complete