Questions tagged [descriptive-complexity]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
104 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 ...
4
votes
3answers
883 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 ...