scientific article; zbMATH DE number 6876262

DOI10.23638/LMCS-14(2:4)2018zbMath1476.03037arXiv1706.08691MaRDI QIDQ4643954

Tony Tan, Eryk Kopczyński

Publication date: 30 May 2018

Full work available at URL: https://arxiv.org/abs/1706.08691

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

bipartite graphsfirst-order spectranon-deterministic exponential timethree-variable logic

Mathematics Subject Classification ID

Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph properties checkable in linear time in the number of vertices
• First-order spectra with one variable
• First-order spectra with one binary predicate
• On the Variable Hierarchy of First-Order Spectra
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• The Spectra of First-Order Sentences and Computational Complexity
• Universal quantifiers and time complexity of random access machines
• Complexity classes and theories of finite models
• A spectrum hierarchy
• Turing machines and the spectra of first-order formulas
• Fifty years of the spectrum problem: survey and new results
• Regular Graphs and the Spectra of Two-Variable Logic with Counting