Nie jesteś zalogowany |
P!=NP
- Prelegent(ci)
- Bartek Klin
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 10 października 2012 14:15
- Pokój
- p. 5870
- 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.
As a corollary, P!=NP over nominal sets.
