Questions tagged [descriptive-complexity]

Classifies problems based on how hard it is to express the problem in some logical formalism.

Filter by
Sorted by
Tagged with
0 votes
0 answers
8 views

Is it possible to define logspace reductions with FO[TC] queries?

Assume that we have a NP problem A, and a NP-complete problem B under logspace reductions. Furthermore, lets assume that we encode the problem A into a relational database $D_A$, and B into another ...
user avatar
1 vote
0 answers
14 views

Decidablility of complexity properties and its relation to finite description method

We describe formal languages with their finite descriptions. For example we can describe a language simply by set-builder ( $\{ x : \phi(x)\}$) or we can describe something with its corresponding ...
user avatar
1 vote
1 answer
28 views

First-order iteration operator example

I am reading on https://en.wikipedia.org/wiki/FO_(complexity)#Iterating that FO[$t(n)$] consists in first-order logic with an iteration operator that iterates $t(n)$ number of times some quantifier ...
user avatar
1 vote
0 answers
4 views

Can we emulate logspace turing machines in FOL extended with TC bounding the number of variables?

As far as I know, Immerman showed that first-order logics extended with transitive closure (TC) captures (non deterministic) logspace (over ordered domains) [1]. That is, any database query that can ...
user avatar
1 vote
0 answers
72 views

Is it known whether PARTITION is NP-complete via first order reductions?

The PARTITION decision problem is defined as follows (taken from COMPUTERS AND INTRACTABILITY from Garey and Johnson): Instance: A finite set $A$ and a size $s(a) \in \mathbb{Z}^{+}$ for each $a \in A$...
user avatar
1 vote
0 answers
98 views

Horn formulas, existential second order logic and the Cardinality constraint

Consider this Problem $P$ as follows: $~$ Given a set $S$ and a constant $K$.. $~$Is there a subset $M$ of $S$, such that $|M| \ge K$? Of course, $P$ can be easily solved in time polynomial in $|S|$.. ...
user avatar
1 vote
0 answers
31 views

What is the space-complexity of a boolean first-order query?

I have the intuitition that, if we implement a (space-efficient) boolean first-order query solver, the amount of consumed memory should depend on the data size (i.e., it should not be constant). ...
user avatar
0 votes
1 answer
51 views

Does FOL extended with least-fixed points satisfy the Compactness Theorem?

I am aware that first-order logics (FOL) satisfies the compactness theorem. That is, if a FOL theory is insatisfiable, a finite subset of the axioms of such theory is insatisfiable too. Is it the case ...
user avatar
3 votes
1 answer
90 views

How to describe Deterministic Transitive Closure in FOL?

In "Finite Model Theory and Its Applications", page 152, it is said that Deterministic Transitive Closure, on ordered finite structures, captures LOGSPACE. Hence, taking into account that ...
user avatar
1 vote
1 answer
43 views

What does Bellantoni-Cook say about Cook-Reckov?

In implicit complexity theory they construct natural programming languages that are complete for various complexity classes. An example, while there are many others, is Bellantoni-Cook where they ...
user avatar
  • 315
0 votes
1 answer
80 views

Descriptive complexity of 3SAT

lately I'm reading about descriptive complexity, which I find is a fascinating branch of computational complexity. I found many formulas in $\exists$$SO$ that describe problems with graphs but none ...
user avatar
  • 1,035
1 vote
1 answer
308 views

Examples of exact computation of Kolmogorov complexity?

First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed ...
user avatar
2 votes
1 answer
54 views

What is the motivation behind " Descriptive Complexity "?

Time and Space are two commons parameters (and also natural parameters) to measure the complexity of the problem. I am not able to understand the motivation behind defining " Descriptive Complexity". ...
user avatar
2 votes
1 answer
49 views

How to understand the notion of boolean query via Immerman's definition

A query is any mapping $I:STRUC[\sigma] \to STRUC[\tau]$ that is polynomially bounded. A boolean query is a map $I_b: STRUC[\sigma] \to \{0,1\}$. A boolean query can also be thought as the susbset: $...
user avatar
3 votes
0 answers
75 views

Computability of Kolmogorov complexity in total languages

It is well known that the Kolmogorov complexity is uncomputable in Turing-complete programming languages. However, what about total programming languages? For example, is the Kolmogorov complexity of ...
user avatar
  • 1,150
1 vote
0 answers
21 views

Structure of numbers in descriptive complexity

Descriptive complexity is a useful way to free yourself from computational considerations when studying complexity. One of those considerations is the encoding of the structures you are working on. ...
user avatar
  • 352
2 votes
0 answers
31 views

Do undecidable problems have no HO query? If so, could I have an example?

In descriptive complexity, HO corresponds to ELEMENTARY. ELEMENTARY is a subset of R, so therefore all HO queries are decidable. Then undecidable problems have no corresponding HO query. Is my ...
user avatar
0 votes
1 answer
537 views

First Order Logic, First Order Logic + Recurrence and SQL

we know that SQL standard is equivalent to First Order Logic (FOL). I've seen at my lecture that graph connectivity cannot be expressed by FOL, so in SQL as well. But we know that we can easily solve ...
user avatar
  • 173
3 votes
1 answer
257 views

Why doesn't descriptive complexity theory solve P = NP?

According to the Wikipedia page on Descriptive complexity theory: In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in ...
user avatar
1 vote
1 answer
41 views

For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases

Let $f$ be some function in some programming language (like C), and we need $n$ bits to store this function. Suppose we have some fixed value $v$ for the argument, then let g() { f(v) } be the ...
user avatar
  • 1,379
3 votes
1 answer
264 views

State complexity of homomorphisms of regular languages

Given a DFA $A = (Q, \Sigma, \delta, q_0, F)$ with $n$ states and a homomorphism $h: \Sigma \to \Gamma^*$. It is easy to see that the family of regular languages is closed under homomorphisms using ...
user avatar
0 votes
1 answer
88 views

NFA state complexity for the complement of EPAL restricted to a fixed length

I've been having trouble proving the next statement: Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA ...
user avatar
1 vote
1 answer
108 views

Reference proof for Second-Order Logic captures Polynomial-Time Hierarchy

I'm looking for a complete proof of $\mathrm{PH=SO}$. The (admittedly few) textbooks and papers i've looked at all either state that it's a corollary from Fagin's Theorem, or leave it as an exercise ...
user avatar
  • 111
0 votes
2 answers
156 views

Descriptive complexity: 3-colorability example

So in Neil Immerman's book http://books.google.co.kr/books?id=kWSZ0OWnupkC&pg=PA113&lpg=PA113#v=onepage&q&f=false, 3-colorability problem in descriptive complexity fashion is expressed ...
user avatar
  • 1
0 votes
3 answers
63 views

A graph in descriptive complexity - is $x$ already a vertex?

So suppose that there is an undirected graph with edge connections known. Now in first-order logic there is quantifier $\forall x$. Then does this automatically refer to vertexes, or can we use ...
user avatar
  • 1
4 votes
1 answer
113 views

First Order interpretation of arbitrary structures as a graph

I am currently trying to get some intuition on the concept of First Order reductions, and have come across this exercise question by Immerman, dubbed "Everything is a Graph". Given some arbitrary ...
user avatar
  • 615
2 votes
0 answers
63 views

Completeness and first order logic with Least fixed point operator (LFP)

Is there any result about the extension of first order logic with least fixed point operator, being complete (as logic in general on infinite structures too) or not? In other words does the Goedel ...
user avatar
4 votes
3 answers
937 views

Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An ...
user avatar
  • 929
2 votes
1 answer
74 views

About proofs in descriptive complexity

In descriptive complexity, we have theorems that look like $\mathrm{ESO} = \mathrm{NP}$ or "on linearly ordered structures, $FO(LFP) = P$", but I don't really understand the proofs of those. For the ...
user avatar
0 votes
1 answer
224 views

NFA and DFA storage cost

In some paper I read, A theoretical worst case study shows that a single regular expression of length $n$ can be expressed as an NFA with $O(n)$ states. When the NFA is converted into a DFA, ...
user avatar
  • 351
8 votes
1 answer
306 views

For what kinds of languages is min |NFA| = Ω(min |DFA|)?

Consider a regular language $L$. Let $D(L)$ be a minimal DFA for $L$ and $N(L)$ be a minimal NFA for $L$ (minimal in the sense of the smallest possible number of states for an automaton that ...
user avatar
1 vote
1 answer
258 views

Expressing complexity class P using first-order logic with LFP

Can anyone show how to express complexity class P using first-order logic with LFP? (descriptive complexity)
user avatar
  • 11
1 vote
1 answer
68 views

Operators in descriptive complexity

When we talk about operators in descriptive complexity, are they something like this: for example, if transitive closure operator $TR$ is available, we can use variable $y$ that we define as $TR(x)$ ...
user avatar
  • 11
3 votes
2 answers
116 views

Lower bound on size of proof that a list of integers is sorted

Suppose we have a list of unbounded integers, written in binary, and we want to write a (formal) proof that the list is sorted in ascending order. Such a proof might look (informally) like: "2 < 3,...
user avatar
5 votes
3 answers
2k views

How to calculate the number of states in designing a Turing machine?

I would like to ask how to determine the number of states when designing a Turing machine from the description for a language? For example: $\qquad \displaystyle L = \{wcw \mid w \in \{0,1\}^*\}.$ I ...
user avatar
5 votes
1 answer
241 views

When does the function mapping a string to its prefix-free Kolmogorov complexity halt?

In Algorithmic Randomness and Complexity from Downey and Hirschfeldt, it is stated on page 129 that $\qquad \displaystyle \sum_{K(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$, where $K(\sigma)\...
user avatar
  • 243
9 votes
1 answer
277 views

Can joins be parallelized?

Suppose we want to join two relations on a predicate. Is this in NC? I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open ...
user avatar
  • 1,538
20 votes
3 answers
339 views

Extension of SQL capturing $\mathsf{P}$

According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator): SQL captures safe ...
user avatar
  • 21.7k