Turing Machines with Atoms

Mikołaj Bojańczyk, Bartek Klin, Sławomir Lasota, Szymon Toruńczyk

2013 · 30 citations · 8 references

Concepts

Abstract

We study Turing machines over sets with atoms, also known as nominal sets. Our main result is that deterministic machines are weaker than nondeterministic ones; in particular, P≠NP in sets with atoms. Our main construction is closely related to the Cai-Furer-Immerman graphs used in descriptive complexity theory.

References

8