What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Questions tagged [descriptive-complexity]

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

50 questions
Filter by
Sorted by
Tagged with
1k views

### Is there a logic without induction that captures much of P?

The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of ...
839 views

### Are there descriptive complexity representations of quantum complexity classes?

The title more or less says it all, but I guess I could add a bit of background and some specific examples I'm interested in. Descriptive complexity theorists, such as Immerman and Fagin, have ...
263 views

### Descriptive complexity characterization of TimeSpace classes

Are there descriptive complexity characterizations for TimeSpace complexity classes like $\mathsf{SC^i}= \mathsf{DTimeSpace}(n^{O(1)},O(\lg^i n))$?
493 views

232 views

### P and Descriptive Complexity

In the Complexity Zoo, it says  that, in descriptive complexity, $P$ can be defined by three different kind of formulae, $FO(LFP)$ which is also $FO(n^{O(1)})$, and also as $SO(HORN)$. However, ...
233 views

### What do dichotomy theorems feed on?

It is well known that certain classes of NP-problems have dichotomy theorems, which guarantee that every task in the class is either NP-complete or is in P. The best known such result is Schaefer's ...
151 views

### Descriptive Complexity characterzation of BPP

We know of descriptive complexity characterizations of classes such as P, and NP, which use First Order logic, and operators. Does BPP have a characterization under descriptive complexity, too(any ...
342 views

### Collapsing of exptime and alternation bounded turing machine

This question was already asked on math overflow, but I did not find any answer to my question (or let say the answer was that up to the knowledge of those people, no answer were known) Let C be a ...
960 views

### How can we express “$P=PSPACE$” as a first-order formula? [closed]

How can we express "$P=PSPACE$" as a first-order formula? Which level of the arithmetic hierarchy contains this formula (and what is the currently known minimum level of the hierarchy that contains it)...
4k views

153 views

### Non-interesting numbers via resource-bounded properties?

There is an old joke about the smallest non-interesting number being interesting in itself (I have heard it attributed to Richard Hamming). This is then used to justify the argument that every number ...
199 views

182 views

### Expressiveness of Infinitary Logic

I'm trying to put together a general picture of the expressiveness of some logics: First-Order Logics, Fixed-Point Logics, (Finite Variable) Infinitary Logics and the respected versions with Counting. ...
195 views

### Logic capturing automorphism-invariant $\mathsf{AC^0}$ properties

Q1. Is there a logic that is computable in polynomial-time which contains all order-invariant properties computable in smaller classes like $\mathsf{AC^0}$ (or $\mathsf{TC^0}$)? Motivation As you ...
674 views

### Context-free Grammar for a Context-free Language Intersecting a Regular Language (get the Maximum Number of Rules)

It is well known that the intersection of $L \cap R$ of a context-free Language $L$ and a regular Language $R$ is context-free. Each proof I have seen constructs a automaton (a PDA) that accepts $L$ ...
158 views

I'm reading a paper which shows the result: $(1)$ There is a $p$-optimal proof system for $\operatorname{TAUT}$. $\Leftrightarrow$ $(2)$ $L_{\leq}$ is a $P$-bounded logic for $P$. Both $(1)$ and $(... 1answer 155 views ### Reductions in Descriptive Complexity Reducing one problem to another are well known in various settings, such as many-one, randomized, truth-table, logspace or a whole slew of other reductions. Descriptive complexity can alternately ... 1answer 146 views ### Descriptive model theory classification of Counting hierarchy Descriptive model theory uses logic to characterize complexity classes How to model Counting Hierarchy PSPACE in descriptive model theory? 2answers 133 views ### Construct proof systems for common algorithmic task, like equivalence of regular expressions A propositional proof system according to Cook and Reckhow for a language$L \subseteq \Sigma^{\ast}$is a deterministic polynomial time function$f : \Sigma^{\ast} \to L$that is onto. For$y \in L$... 1answer 126 views ### What is FO(REGULAR)? (The descriptive complexity equivalent of NC1) According to Immerman's Descriptive Complexity diagram, there is a logic called$\mathsf{FO(REGULAR)}$which captures$\mathsf{NC}^1$. However, I can't find the reference where this logic is defined. ... 1answer 290 views ### What is a commutative transitive closure operator? When reading about descriptive complexity theory, I have read about a "commutative transitive closure operator". I understand transitive closure operators, but what is a commutative transitive closure ... 3answers 146 views ### Searching for matching queries Suppose you have a large set of queries (could be in SQL form, but conceivably the same problem exists for search engine query strings or Lucene expressions, etc...) stored and you want to know which ... 0answers 57 views ### Inexpressibility of Second order In finite model theory, Ehrenfeucht-Fraïssé games gives us tools to prove inexpressibility results for FOL. Pebble games do the same for infinitary logic with finitely many variables. Do we have such ... 1answer 71 views ### Infinitary Counting Logics: 1-sorted vs. 2-sorted framework There are two ways to extend infinitary logic with counting: Grädel's way (cf. p. 11): We extend$L_{\infty\omega}$by introducing a counting existential quantifier: $$\mathcal{A} \models \exists^{... 1answer 311 views ### Least fixed point logic is efficiently \operatorname{P}-bounded for \operatorname{P} \Leftrightarrow L_\leq is a logic for \operatorname{P} A least-fixed point (LFP) formula is \leq m-invariant iff f.a. structrues \mathcal{A} with |A| \leq m and all orderings <_1,<_2 on A$$(\mathcal{A},<_1) \models_{LFP} \varphi \... 0answers 109 views ### Proof of SAT is complete for NP via first-order reductions So I have been reading this: https://people.cs.umass.edu/~immerman/book/ch7.pdf I do not understand the proof of theorem 7.16, which says that SAT is complete for NP via first-order reductions. My ... 0answers 134 views ### Do problems have to be statable in$\Pi_1\$ to use Levin's universal search to find short proofs if P=NP

In If P=NP, could we obtain proofs of Goldbach's Conjecture etc.? it talks about the hypothetical world where P=NP and using the proof of it to prove a problem/theorem assuming that it has a short ...