4
votes
Accepted
What is the impact of encodings of sparse structures on the complexity of the model checking problem?
I don't know of any natural logic, but the following is in any case a logic for which the combined complexity of the model-checking problem is different for matrix and list encodings.
First, we know ...
- 776
Only top scored, non community-wiki answers of a minimum length are eligible