DIscrete Math

Sat ∈ NP

True

Sat ∈ P

Open

G.I. ∈ P

Open

G.I. ∈ NP

True

Problem R ∈ P then then R ∈ NP

True

R ∈ RP then R ∈ NP

Open

P <_NP

True

P = NP

Open

NP <_P

Open

If G.I ∈! NP then P ≠NP

True

If G.I ∈! P then P ≠ NP

Open

G.I ∈ P

True

If A,B are in sets and there exists s.t x ∈ A but x ∈! B then A ≠ B

True

Halting is decidable

false

Halting is in NP

False

Satisfiablity is decidable

True

The Halting Problem is a decision problem

True

Sat ∈ P

Open

Our algorithim for Sat has worst case time complexity

False

Primality ∈ NP

True

Primality ∈ P

True

If G.I ∈ P then P = NP

Open

If Sat ∈ P then P = NP

True

If Sat ∈ P then G.I ∈ P

True

If G.I !∈ P then Sat !∈ P

True

If Sat ∈ P then G.I ∈ P

Open