Complexity and NP-Completeness

Question 1

What is P?

Answer 1

all the problems SOLVABLE in polynomial time

Question 2

What is a decision problem?

Answer 2

The answer is either yes or no

Question 3

What is NP?

Answer 3

decision problem SOLVABLE in NON-deterministic polynomial time

Question 4

What does non-deterministic mean?

Answer 4

choice during running is not determined by input. ARBITRARY GUESS AMONG MANY POSSIBILITIES

Question 5

When is a problem A reducible to a problem B?

Answer 5

• when ANY instance a of A can be transformed into some instance b of B
• transformation takes poly time
• answer a “yes” iff answer of b “yes”

Question 6

If A reduces to B which one is harder to solve?

Answer 6

they are both equally hard to solve

Question 7

What are the steps of proving language L is NP complete by reduction?

Answer 7

1. Prove LeNP
2. Select known NP-Complete Language L’
3. Describe algorithm the computes f mapping every instance of xeL’ to instance f(x) of L
4. Prove xeL’ iff f(x)eL for all xe{0,1}*
5. Prove that f runs in polynomial time

Question 8

When is problem x NP-complete?

Answer 8

xeNP && xeNP-hard

Question 9

When is a problem NP-hard?

Answer 9

When every NP problem reduces to x

Question 10

Informal way of describing NP-completeness

Answer 10

Problem is EXACTLY as hard as everything in NP

Question 11

Informal way of describing NP-hardness?

Answer 11

Problem is no easier than everything in NP

Question 12

Informal way of describing NP?

Answer 12

Problem is no harder than everything in NP

Question 13

If problem BeP and A is reducible to B where does A belong?

Answer 13

P

Question 14

If problem BeNP and A is reducible to B where does A belong?

Answer 14

NP