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

learn more… | top users | synonyms

2
votes
1answer
32 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 ...
0
votes
1answer
91 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, ...
6
votes
1answer
176 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 ...
6
votes
0answers
50 views

Interval density of time bounded Kolmogorov complexity

The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to ...
1
vote
1answer
56 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)
1
vote
1answer
53 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)$ ...
3
votes
2answers
82 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 < ...
5
votes
3answers
289 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 ...
3
votes
1answer
145 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 ...
9
votes
1answer
203 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 ...
13
votes
3answers
234 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 ...