3
$\begingroup$

I know that given problem is in $\mathsf{FP}$: if given formula is satisfiable, then it is only needed to find out how many connected components equality (undirected) graph has. In fact problem is to count the amount of connected components.

However, is it possible to solve it using only log space? Is then the given problem is $\mathsf{FL}$-complete? Or, maybe, this problem is complete somewhere in $\mathsf{AC}$?

$\endgroup$
  • $\begingroup$ Logspace functions can have polynomial size output. We usually only measure the space in the work tape. The input tape is read only, and the output tape is write only. $\endgroup$ – Yuval Filmus Aug 9 '17 at 14:48
  • $\begingroup$ So you're asking if we can count the number of components in an undirected graph in logspace? Have I understood that correctly? $\endgroup$ – D.W. Aug 9 '17 at 16:27
  • $\begingroup$ @D.W. I think yes since it solves the problem. $\endgroup$ – rus9384 Aug 9 '17 at 16:55
0
$\begingroup$

The given problem is in $\mathsf {FL}$:

  1. Solve if it is satisfiable. Let the result be number $s$. Can be done in logarithmic space.
  2. Set $t=0$.
  3. Count the number of clauses of form $(a\oplus \overline a)$ where $a$ does not appear in any other clause except clauses identical to that one. For each such clause increase $t$ by $1$.

Step 3 can be performed in log space as follows:

for every i in V:
    flagIndependent = true
    flagAppears = false
    for every j in C:
        if C_j isIdentical(`(x_i xor not(x_i))`):
            flagAppears = true
        elseif C_j contains(`x_i`):
            flagIndependent = false
    t += flagAppears * flagIndependent

Two variables i and j take space $\log(|V|)$ and $\log(|C|)$ respectively. Variables flagIndependent and flagAppears take $1$ bit each. Functions checking clauses also require $O(\log(n))$ space at most. Therefore the total space used is logarithmic.

The answer is $s2^t$.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.