All Questions
Tagged with linear-temporal-logic parameterized-complexity
1 question
4
votes
1
answer
164
views
Is model checking PSpace-hard *in formula size*?
Sistla/Clarke proved [SC82] that the LTL model-checking problem is PSpace-complete.
Sometimes people write that this problem is "PSpace-hard in $|\phi|$" (e.g. [LP85]). What does this mean formally?
...
- 1,095