2013 · 30 citations · 8 references
ComputingComputer ScienceMathematicsAlgorithmsSet TheoryTheory Of ComputationComputational ComplexityDescriptive ComplexitySet SystemsTuring MachinesDescriptive Complexity Of NpDescriptive Complexity Of PDescriptive Set-theoretic ComplexityDeterministic Turing MachinesNondeterministic ComplexityNondeterministic Turing MachinesTuring Machine Complexity
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.
8
William A. Howard · Journal of Symbolic Logic · 1984 · 840 citations
Automata theory in nominal sets
Bartek Klin · 2015 · 104 citations
Mikołaj Bojańczyk, Bartek Klin, Sławomir Lasota · 2011 · 85 citations