New answers tagged np-complete
1
There are two results this could plausibly be which nicely contrast each other - they differ on whether we look at finite or infinite structures:
(Turing, following Godel) The validity problem for first-order logic on arbitrary structures in a sufficiently rich language is $\Sigma^0_1$-complete; for example, the set of (codes of) sentences true in every ...
Top 50 recent answers are included