Turing Machines with Atoms

Mikolaj Bojanczyk,Bartek Klin,Slawomir Lasota,Szymon Torunczyk

LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science（2013）

引用 63|浏览5

暂无评分

摘要

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.

查看译文

关键词

Turing machines,atoms,computational complexity,graph theory,set theory,Cai-Furer-Immerman graphs,P≠NP,Turing machines,atoms,descriptive complexity theory,nominal sets,nondeterministic machines,Sets with atoms, Turing machines

AI 理解论文

溯源树

样例

生成溯源树，研究论文发展脉络

Chat Paper

正在生成论文摘要