in nominal sets

Speaker(s)

Bartek Klin

Affiliation

Uniwersytet Warszawski

Date

Oct. 10, 2012, 2:15 p.m.

Room

room 5870

Title in Polish

P!=NP

Seminar

Seminar Automata Theory

---

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.

---