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.