P,NP,NP-Hard and NP-Complete

Mindtwister: complexity of problems


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.

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.

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

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.

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.

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.

Nov 16, 2020

[+] 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   
- 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.


Fun with Image Maps and SVGs via benji February 20, 2024

Over the past few weeks I've been playing around with making some images on my website interactive. My "informatics" class in high school taught us some basic HTML. By basic I mean in notepad and writing everything by hand, saving to a...

Goblin Week 2024 via Helvetica Blanc January 26, 2024

It snuck up on me, but I managed to draw my little goblins to celebrate the week! I love my children - they're like awful Pikmin. I've uploaded the whole parade as a print, as well as individual prints for each goblin. There's something very fu…

How to trust gpg keys via Travis Shears Personal Site October 27, 2023

After moving some GPG keys to a new computer I kept getting these trust warnings. It is NOT certain that the key belongs to the person named in the user ID.If you * really * know what you are doing, you may answer the next question with yes. Use this key a…

Generated by openring from webring