Skip to main content

Questions tagged [descriptive-complexity]

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

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
21 votes
0 answers

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))$?
Kaveh's user avatar
  • 21.6k
20 votes
0 answers

Model-checking for three-variable logics and restricted structures

Denote the $k$-variable fragment of logic $L$ by $L^{(k)}$. The model-checking problem for a logic $L$ with respect to a class of structures $C$, denoted $MC(L,C)$, is the decision problem $MC(L,C)...
András Salamon's user avatar
19 votes
0 answers

To what extent MSO = WS1S, when adding relations?

[This question has been asked on MathOverflow with no luck a month ago.] Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma =\{a_1, \ldots, a_n\}$, I define two ...
Michaël Cadilhac's user avatar
15 votes
0 answers

Proof assistant formalizations of Finite Model Theory

I'm wondering if anyone knows of a formalization (even limited) of any part of finite model theory in any of the major proof assistants. (I'm most familiar with Coq, but Isabelle, Agda, etc. would ...
Marc Hamann's user avatar
  • 2,924
11 votes
0 answers

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 ...
user3483902's user avatar
  • 1,261
10 votes
0 answers

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 ...
Arthur MILCHIOR's user avatar
5 votes
0 answers

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 ...
Kaveh's user avatar
  • 21.6k
4 votes
1 answer

Implicit characterization of sublogarithmic space

Let $SUBLOG = DSPACE(o(\log(n)) \setminus DSPACE(O(1))$ be the set of languages decidable with less than logarithmic space, but more than a constant amount of space, on a multi-tape Turing machine ...
Jake's user avatar
  • 1,214
3 votes
0 answers

Extending fagin’s theorem for #P (for arbitary structure)

While i am reading Descriptive complexity of #P functions (Saluja) in theorem 1 he state that #FO coincides #P on ordered structures. This is a corollary from fagin’s theorem. I have read fagin’s ...
Omid Yaghoubi's user avatar
2 votes
0 answers

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 ...
wazdra's user avatar
  • 121
1 vote
0 answers

Are classes of graphs represented by adjacency matrix ordered structures?

We know that FO[LFP] captures PTIME on the class of ordered structures. However, I have difficulties interpreting this result. From what I understand, it means that, given a constant, finite alphabet $...
Paweł Balawender's user avatar
1 vote
0 answers

Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality ...
Erfan Khaniki's user avatar
1 vote
0 answers

Proof of SAT is complete for NP via first-order reductions

So I have been reading this: I do not understand the proof of theorem 7.16, which says that SAT is complete for NP via first-order reductions. My ...
Geckabor's user avatar
1 vote
0 answers

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 ...
time's user avatar
  • 21
0 votes
0 answers

Does Descriptive Complexity techniques have the naturalisation barrier?

I wished to know if the proof attempts at separation of complexity classes via the methods outlined by Descriptive Complexity theorists naturalise? By naturalise I'm talking about the Idea of Natural ...
Ramit's user avatar
  • 21
0 votes
0 answers

Questions about the definition of the Quantum Turing Machine

I am trying to have a better understanding of the definition of the Quantum Turing Machine. My questions: If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
Omar Shehab's user avatar
-3 votes
1 answer

Can one do descriptive complexity theory using abstract state machines?

I learned about ASM recently and was interested how it could used for descriptive complexity theory. Such link seems natural to me: you can give construction of algebraic model for formula as an ASM. ...
uhbif19's user avatar
  • 315