# A Restricted Second-Order Logic for Non-deterministic Poly-Logarithmic Time

@article{Ferrarotti2020ARS, title={A Restricted Second-Order Logic for Non-deterministic Poly-Logarithmic Time}, author={Flavio Ferrarotti and Sen{\'e}n Gonz{\'a}lez and Klaus-Dieter Schewe and Jos{\'e} Maria Turull Torres}, journal={ArXiv}, year={2020}, volume={abs/1912.00010} }

We introduce a restricted second-order logic $\mathrm{SO}^{\mathit{plog}}$ for finite structures where second-order quantification ranges over relations of size at most poly-logarithmic in the size of the structure. We demonstrate the relevance of this logic and complexity class by several problems in database theory. We then prove a Fagin's style theorem showing that the Boolean queries which can be expressed in the existential fragment of $\mathrm{SO}^{\mathit{plog}}$ corresponds exactly to… Expand

#### Topics from this paper

#### 2 Citations

Proper Hierarchies in Polylogarithmic Time and Absence of Complete Problems

- Computer Science, Mathematics
- FoIKS
- 2020

This paper shows that the descriptive complexity theory of polylogarithmic time is taken further showing that there are strict hierarchies inside each of the classes of the hierarchy. Expand

Completeness in Polylogarithmic Time and Space

- Computer Science
- ArXiv
- 2020

An alternative notion of completeness inspired by the concept of uniformity from circuit complexity is developed and proved and it is shown that complete problems can still play an important role in the study of the interrelationship between polylogarithmic and other classical complexity classes. Expand

#### References

SHOWING 1-10 OF 31 REFERENCES

The Polylog-Time Hierarchy Captured by Restricted Second-Order Logic

- Mathematics, Computer Science
- 2018 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)
- 2018

The problem, which Turing machine complexity class is captured by Boolean queries over ordered relational structures that can be expressed in second-order logic, is investigated and the relevance of this logic and complexity class by several problems in database theory is demonstrated. Expand

A Second-Order Logic in Which Variables Range over Relations with Complete First-Order Types

- Computer Science
- 2010 XXIX International Conference of the Chilean Computer Science Society
- 2010

The complexity class NP$^F$ is defined by using a variation of the relational machine of S. Abiteboul and V. Vianu and it is proved that this complexity class is captured by $\Sigma^{1,F}_1$. Expand

Second-Order Logic over Strings: Regular and Non-regular Fragments

- Computer Science
- Developments in Language Theory
- 2001

An exhaustive classification of the regular and nonregular prefix classes of general second-order logic, and derive of complexity results for the corresponding model checking problems. Expand

Existential second-order logic over graphs: charting the tractability frontier

- Mathematics, Computer Science
- Proceedings 41st Annual Symposium on Foundations of Computer Science
- 2000

A dichotomy holds, i.e., each prefix class of existential second-order logic either contains sentences that can express NP-complete problems or each of its sentences expresses a polynomial-time solvable problem. Expand

Choiceless Polynomial Time

- Computer Science, Mathematics
- Ann. Pure Appl. Log.
- 1999

This work attempts to capture the choiceless fragment of PTime, a version of abstract state machines (formerly called evolving algebras) that is to replace arbitrary choice with parallel execution and is more expressive than other PTime logics in the literature. Expand

Capturing Complexity Classes by Fragments of Second-Order Logic

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1992

It is shown that all these logics collapse to their existential fragments and are strictly weaker than previously known logics for these classes and fail to express some very simple properties. Expand

Existential second-order logic over graphs: Charting the tractability frontier

- Mathematics, Computer Science
- JACM
- 2004

This article completely characterize the computational complexity of prefix classes of existential second-order logic in three different contexts: (1) over directed graphs, (2) over undirected graphs with self-loops and (3) over undirected graphs without self-Loops. Expand

Existential second-order logic over strings

- Mathematics, Computer Science
- JACM
- 2000

ESO and ESO are the maximal standard ESO-prefix classes contained in MSO, thus expressing only regular languages, and the following dichotomy theorem is proved: An ESO prefix-class either expresses onlyregular languages (and is thus in ESO), or it expresses some NP-complete languages. Expand

The complexity of theorem-proving procedures

- Computer Science, Mathematics
- STOC
- 1971

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a… Expand

A restricted second order logic for finite structures

- Mathematics
- 1998

We introduce a restricted version of second order logic SOω in which the second order quantifiers range over relations that are closed under the equivalence relation ≡k of k variable equivalence, for… Expand