What do log-equivalent and log-complete mean?

209 Views Asked by At

I'm reading the paper The Complexity of Satisfiability Problems by Thomas Schaefer(1978). In the paper, he mentions the phrases "log-equivalent" and "log-complete." Searching through the Google results does not seem to give me anything related to complexity theory. I'm guessing it has to do with log-space.

As an example, let $SAT_C(S)$ be the satisfiability problem with constants allowed. The following are statements in the paper:

"$SAT_C(S)$ is log-equivalent to the graph reducibility problem."

"$SAT_C(S)$ is log-complete in P"

"$SAT_C(S)$ is log-complete in NP."

1

There are 1 best solutions below

0
On BEST ANSWER

I hope that you didn't give up and found an answer in appendix of that paper, but since your question is the only related google's result I think that it's worth to put some definitions here.

Let's start with this two definitons:

A function $f$ is log-space computable if there is a deterministic Turing machine which on input $w \in \Sigma^*$ outputs $f(w)$ and uses at most $O(log |w|)$ memory. It's worth noticing that since there is at most $|\Sigma|^{O(log |w|)}$ different states of tape, then such machine works in polynomial time.

For languages (problems) $A, B \subseteq \Sigma^{*}$, A is log-space reducible to $B$ (denoted by $A \leq_{log} B$) iff there is a log-space computable function f such that for all $w \in \Sigma^{*}$, $w \in A$ iff $f(w) \in B$. Observation from previous definition implies that, problem $A$ is also polynomial-time reducible to problem $B$.

And back to phrases from you question:

Problems $A$ and $B$ are log-equivalent iff $A$ is log-space reducible to $B$ and vice versa ($A \leq_{log} B \land B \leq_{log} A$).

Problem $A$ is log-complete in class of problems $\mathcal{C}$ iff $A$ is an element of $\mathcal{C}$ and for each problem $B$ from $\mathcal{C}$, $B$ is log-space reducible to $A$ ($A \in \mathcal{C} \land \underset{B\in \mathcal{C}}{\forall} B \leq_{log} A$).