# P,NP,NP-Hard and NP-Complete

Mindtwister: complexity of problems

# Overview

**Hardness**- Problem A is “harder” (at least not easier) than problem B, if B can be seen as a special case of A , or B can be transformed into A, which means B can be solved by solving A.

**P(polynomial Time)**

A problem is P: it can be solved in polynomial time.

**NP(nondeterministic polynomial time)**

A problem is NP: a given answer can be examed whether it is correct in polynomial time.

**P=NP?**- It is obvious that every P problem is a NP problem. But is vice versa?
This is an important but unsolved problem:
`if a problem is NP, is it P?`

In other words: if P=NP stands, then any NP problem can be solved in polynomial time. This would be great! Because finding an algorithm to justify an answer is way easier than finding an algorithm to solve the problem itself.

**co-NP**

A desicion problem $x$ is in co-NP $\iff \overline{x}$ is in NP: We can deny an given answer in polynomial time.

**PH**

Polynomial Hierarchy, PH is an extension of NP. PH is contained in PSPACE. [TODO]
can be defined with oracle machines or alternating turing machines. We don’t know yet if PH and P are different. If P=NP then P=PH.

**NP-Hard**

A NP-hard problem is “harder” to solve than every single NP problem. Also, every
NP problem can be transformed into a NP-hard problem **in polynomial time**.

**NP-Complete**

if a problem NP-hard, and itself is a NP, then it’s called NP-Complete.
NPC problems are the hardest problems in NP, solving one of the NPC means solving
all the NPs (and other NPCs).

**PSPACE, PSPACE-hard and PSPACE-Complete**

Similar to above, but dont care about time, instead, focus on the storage(memory) space.
It’s proved that, all P, NP, PH Problems are in PSPACE. It’s yet to prove, whether
P and PSPACE are the same.

##
**[+] click to leave a comment [+]**

the comment system on this blog works via email. The button below will generate a mailto: link based on this page's url and invoke your email client - please edit the comment there! [optional] even better, encrypt the email with my public key - don't modify the subject field - specify a nickname, otherwise your comment will be shown as anonymous - your email address will not be disclosed - you agree that the comment is to be made public. - to take down a comment, send the request via email.>> SEND COMMENT <<