Tagged Questions

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

learn more… | top users | synonyms

0
votes
1answer
37 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 ...
1
vote
1answer
22 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 ...
0
votes
1answer
35 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 ...
0
votes
3answers
39 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 ...
4
votes
1answer
41 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 ...
2
votes
0answers
17 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 ...
3
votes
3answers
156 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 ...
2
votes
1answer
39 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
99 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
182 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
53 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
71 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
54 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
85 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
331 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
152 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
212 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 ...
14
votes
3answers
240 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 ...