Find link

language:

Find link is a tool written by Edward Betts.

searching for Descriptive complexity theory 6 found (24 total)

alternate case: descriptive complexity theory

Fagin's theorem (599 words) [view diff] exact match in snippet view article find links to article

Fagin's theorem is the oldest result of descriptive complexity theory, a branch of computational complexity theory that characterizes complexity classes

PSPACE (982 words) [view diff] exact match in snippet view article find links to article

APTIME or just AP. A logical characterization of PSPACE from descriptive complexity theory is that it is the set of problems expressible in second-order

Two-variable logic (384 words) [view diff] exact match in snippet view article find links to article

in Computer Science, 1997. Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.

Spectrum of a sentence (1,365 words) [view diff] exact match in snippet view article find links to article

with the successor function. Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential

Colour refinement algorithm (899 words) [view diff] exact match in snippet view article find links to article

1979.8. Retrieved 2024-01-18. Grohe, Martin. "Finite variable logics in descriptive complexity theory." Bulletin of Symbolic Logic 4.4 (1998): 345-398.

Alexei Semenov (mathematician) (3,342 words) [view diff] exact match in snippet view article

solved a problem of Andrey Kolmogorov from his work originated descriptive complexity theory. He also contributed to the foundations of the theory of algorithms