P!=NP

Prelegent(ci)

Bartek Klin

Afiliacja

Uniwersytet Warszawski

Termin

10 października 2012 14:15

Pokój

p. 5870

Tytuł w języku angielskim

in nominal sets

Seminarium

Seminarium „Teoria automatów”

---

After a brief recap on nominal sets, and following a standard definition of deterministic and nondeterministic Turing machines, I will show a nominal language that is in NP, but is not deterministically recognizable by a nominal Turing machine.

As a corollary, P!=NP over nominal sets.

---