patternMinor
Complexity of self-reducible set
Viewed 0 times
setreduciblecomplexityself
Problem
I am trying to solve the following problem:
A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where $\left|l(x)\right| < \left|x\right|$, $\left|r(x)\right| < |x|$, and $l$ and $r$ are both deterministic polynomial time computable functions. What is the maximum possible complexity of a self-reducible set (you can choose $l$ and $r$)? For your complexity estimate, prove upper and lower bounds.
Now, I think $S \in P$, because to decide if $x \in S$, we can simply iterate $l$ and $r$ until they both get to $1$ or not, and since the length must decrease each time, the time taken will be polynomial in the length of $x$. Is this correct?
Also, what could the problem mean by a lower bound? By defining $l$ and $r$ to be $1$, we get $\Sigma^*$, the set of all strings, which is regular...
A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where $\left|l(x)\right| < \left|x\right|$, $\left|r(x)\right| < |x|$, and $l$ and $r$ are both deterministic polynomial time computable functions. What is the maximum possible complexity of a self-reducible set (you can choose $l$ and $r$)? For your complexity estimate, prove upper and lower bounds.
Now, I think $S \in P$, because to decide if $x \in S$, we can simply iterate $l$ and $r$ until they both get to $1$ or not, and since the length must decrease each time, the time taken will be polynomial in the length of $x$. Is this correct?
Also, what could the problem mean by a lower bound? By defining $l$ and $r$ to be $1$, we get $\Sigma^*$, the set of all strings, which is regular...
Solution
Suppose for simplicity that $|l(x)| = |r(x)| = |x|-1$. If $L(n),R(n)$ are the time complexities for computing $l,r$ on inputs of length $n$, then the time complexity for computing membership in $S$ satisfies the recurrence
$$ T(n) \geq L(n) + R(n) + 2T(n-1). $$
Let's ignore for a moment the stuff not included in this recurrence, and imagine that we actually had equality. Even if $R(n) = L(n) = 0$, the complexity is $2^n T(0) = \Theta(2^n)$, and so the overall complexity is $\Omega(2^n)$ in this case (taking into account the stuff I didn't include in the recurrence). You can use the master theorem to get a corresponding upper bound.
If $l,r$ shrink their input more, the complexity could improve. For example, if $|l(x)|,|r(x)| \leq c|x|$ for some $c < 1$, the complexity will be polynomial (using the master theorem). In the extreme case that $|l(x)| = |r(x)| = 0$, the complexity is constant (or linear, depending on the computation model).
So far we have seen an exponential upper bound and an example where the complexity is constant. The trivial algorithm has exponential time complexity in the worst case, but it is not necessarily the best algorithm. Consider, however, the set $S$ consisting of all tautologies. It is not too difficult to make $S$ self-reducible according to this definition ($l$ and $r$ substitute True and False for one of the variables), and so we get a self-reducible set with is coNP-complete. This shows that unless P=NP, there exist self-reducible sets which cannot be decided in polynomial time.
$$ T(n) \geq L(n) + R(n) + 2T(n-1). $$
Let's ignore for a moment the stuff not included in this recurrence, and imagine that we actually had equality. Even if $R(n) = L(n) = 0$, the complexity is $2^n T(0) = \Theta(2^n)$, and so the overall complexity is $\Omega(2^n)$ in this case (taking into account the stuff I didn't include in the recurrence). You can use the master theorem to get a corresponding upper bound.
If $l,r$ shrink their input more, the complexity could improve. For example, if $|l(x)|,|r(x)| \leq c|x|$ for some $c < 1$, the complexity will be polynomial (using the master theorem). In the extreme case that $|l(x)| = |r(x)| = 0$, the complexity is constant (or linear, depending on the computation model).
So far we have seen an exponential upper bound and an example where the complexity is constant. The trivial algorithm has exponential time complexity in the worst case, but it is not necessarily the best algorithm. Consider, however, the set $S$ consisting of all tautologies. It is not too difficult to make $S$ self-reducible according to this definition ($l$ and $r$ substitute True and False for one of the variables), and so we get a self-reducible set with is coNP-complete. This shows that unless P=NP, there exist self-reducible sets which cannot be decided in polynomial time.
Context
StackExchange Computer Science Q#40156, answer score: 3
Revisions (0)
No revisions yet.