# Questions tagged [descriptive-complexity]

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

28 questions
Filter by
Sorted by
Tagged with
46 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 ...
35 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 ...
32 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". ...
35 views

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: $... 0answers 47 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 ... 0answers 11 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. ... 0answers 26 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 ... 1answer 306 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 ... 1answer 148 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 ... 1answer 34 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 ... 1answer 201 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 ... 1answer 69 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 ... 1answer 90 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 ... 2answers 149 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 ... 3answers 60 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 ... 1answer 94 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 ... 0answers 56 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 ... 3answers 732 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 ... 1answer 61 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 ... 1answer 168 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, ... 1answer 229 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 ... 1answer 217 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) 1answer 61 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)$... 2answers 112 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,... 3answers 1k 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 ... 1answer 209 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)\...
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 ...
### 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 ...