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}$?

Assuming that answer is given as $2^k$, where $k\in\{0,\mathbb{N}\}$, where $k$ is number of connected components. Otherwise we'd need polynomial space to print the number.

  • $\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

Your Answer

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

Browse other questions tagged or ask your own question.