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 ?
NP vs co-NP:
- A problem can be both NP and co-NP (eg: Primality)
- NP => A positive solution can be verified in P time
- co-NP => A negative solution can be refuted in P time
- Primality:
- Proof of primality can be checked in P-time (Eg: AKS)
- Compositeness proof of a number is prime factors => Can be checked in P-time
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