finite-model theory

views updated

finite-model theory A branch of the study of computational complexity in which complexity classes are characterized by definitions that use logical languages applied to finite structures. Connections between resource bounds and formal definitions constitute a research area with great potential.