Classifies problems based on how hard it is to express the problem in some logical formalism.
6
votes
0answers
37 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 ...
0
votes
0answers
160 views
Proof that P != NP (proof-check) [closed]
A proof that P != NP.
Warning: This proof uses descriptive complexity. I would post it on cstheory.stackexchange.com , but they don't want P vs. NP proofs.
The argument that P != NP is ...
1
vote
1answer
33 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
50 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
71 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
224 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
116 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 ...
7
votes
1answer
193 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
213 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 ...
