2
$\begingroup$

Time and Space are two commons parameters (and also natural parameters) to measure the complexity of the problem. I am not able to understand the motivation behind defining " Descriptive Complexity". I search on the internet and find out that it is the complexity of expressing some property of the input. Take the example of the sorting problem. Time and Space seems to be a natural choice. I am unable to come up with an example or a problem which immediately implies the importance of defining the " Descriptive Complexity ".

Question : What is the motivation behind " Descriptive Complexity "?

Improve this question
$\endgroup$
2
$\begingroup$

If you're interested in logic, "what problems can you express in this logic?" is a completely natural question.

If you're interested in computational complexity, descriptive complexity gives another tool that you might be able to use to prove things. For example, the fact that existential second-order logic exactly corresponds to NP means that, if you can prove either (a) no logic corresponds exactly to P or (b) there is a logic that corresponds exactly to P but it has different expressive power to existential second-order, then you've proven that P$\,\neq\,$NP. And it's turned out that trying to prove it via logic has been exactly as fruitful as every other approach! 😉

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy