0
$\begingroup$

I am trying to understand the complexity of a problem that involves solving some $\mathsf{PSPACE}$-complete problem exponentially many times. Namely, one can imagine $\Xi=\{\phi_1,\ldots,\phi_n\}$ to be a set of formulas of modal logic $\mathbf{K}$, and our problem is to tell whether the following formulas are satisfiable for every $\Gamma\subseteq\Xi$:

$$\xi_\Gamma=\bigwedge\limits_{\phi\in\Gamma}\phi\wedge\bigwedge\limits_{\chi\notin\Gamma}\neg\chi$$

Thus, the input is $\Xi$ and the output is $2^{|\Xi|}$ answers ‘yes’ or ‘no’ corresponding to whether their respective $\xi_\Gamma$ is satisfiable.

I was thinking that we need exponential space because we first need to define $\xi_\Gamma$'s and keep them in the memory for the duration of the decision process. And even if we do it with labels for formulas in $\Xi$, instead of actual formulas, there are still exponentially many of those. (Note that we, of course, cannot solve this cycling through $\Xi$ one formula at a time because a conjunction of two satisfiable formulas does not have to be satisfiable.)

But maybe I am wrong, and we do not actually need to do this, and it is possible to give exponentially many answers without utilising an exponential amount of space. If so, what is the complexity of such tasks?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

You do not need exponential space for this, and you can in fact solve this problem by iterating over subsets one by one. The key point is that there is a way to itereate over all possible sets without explicitly writing them all down first. Perhaps the easiest way to do this is to encode a subset of $\{1,\ldots,n\}$ as an $n$-bit binary number, and just increase this number. For example, for the set $\{A,B,C\}$, i.e.,$n=3$, you would have the following iteration over subsets:

$000\to \emptyset$, $001\to \{A\}$, $010\to \{B\}$, $011\to \{A,B\}$ $,\ldots,$ $111\to \{A,B,C\}$

Thus, write this binary vector (polynomial space), and construct the corresponding formula for the vector (still polynomial space). Check satisfiability (still polynomial space), and then erase the formula and increment the vector by 1, and repeat.

If at any point the formula is not satisfiable, you're done. Otherwise, when you finished iterating over all $2^n$ vectors, you are also done.

Improve this answer
$\endgroup$
7
  • $\begingroup$ But I do need to have answers about each formula corresponding to the subset in the end. I.e., the output is not a singular answer but a sequence of yes-no's. And since there are exponentially many such formulas, do I not need to have exponential space just to state the answer? $\endgroup$ Commented Oct 5 at 9:42
  • 3
    $\begingroup$ Ahh, I understood from your question that you want to tell whether all the formulas are satisfiable, not which ones are satisfiable. For the latter you do need exponential space, because like you say: the answer is exponential. But this is somewhat "cheating". If you take a model with an output tape, then you can still only use polynomial computing space, while outputting the satisfiable formulas. $\endgroup$ Commented Oct 5 at 9:52
  • $\begingroup$ Thanks! Unfortunately, for my purposes, I will need to handle the satisfiable formulas in the next steps, so I cannot just put them on the output tape and leave them be. $\endgroup$ Commented Oct 5 at 10:28
  • 1
    $\begingroup$ If your next algorithm is also PSPACE, you might be able to do them both in sequence, "on-the-fly". $\endgroup$ Commented Oct 5 at 10:43
  • $\begingroup$ You mean, if the next algorithm can be computed in space polynomial in the size of the original input. It would have to be a polylog-space algorithm in terms of its own input, which is exponential in the original input size. $\endgroup$ Commented Oct 5 at 13:11

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.