Decidability/Semidecidability and P,NP... Computational Complexity

Question

For an exam im studying First Order Logic and at the same time im studying linear programming for another exam.

Now a question came to me, but i didnt succeed in finding an answer.

Is there any correlations beetween the concept of decidability (but also soundness and completeness ) and the concept of P,NP,NP-hard.... of Computational complexity

Answer 1

Expressibility in certain logics is sometimes equivalent to complexity class membership. For instance, First Order Logic with a (commutative) transitive closure operator yields $L$/$NL$.

See https://en.wikipedia.org/wiki/Descriptive_complexity_theory

Answer 2

You are certainly onto something!

In computability, we are interested in proving whether a certain problem is decidable suppossing we have arbitrarily large memory and time to execute our programs.

This defines two large classes of problems, namely the class of decidable problems R and the class of semidecidable problems called SR. Obviously, R < SR.

In computational complexity, we try to be more precise, and figure out what can be computed when we impose certain limits on the memory and time available to us.

Thus, all the classes studied in computational complexity are subsets of the class of decidable problems R.

However, the techniques used in one field and the other are often really different, because one key complication: while in computability we are allowed to assume that all models of computation are equivalent, in computational complexity this assumption breaks (as far as we know, the proofs have been proved elusive). For example, we believe that what can be computed in polynomial time in a quantum computer (BQP class) is strictly larger than what can be computed in a classical computer (PP class).