Can every infinite set in P be partitioned into two infinite subsets, each also in P? Uwe Schöning answers this question in the affirmative in the Winter 1982 SIGACT News. Let's generalize the question by saying that a set A

*splits*a set B if both A∩B and A∩B are infinite. Schöning really shows the more general result that any infinite recursive set can be split by a polynomial-time computable set.Playing with this splitting notion yields lots of potential homework questions. Try these:

- Show that every infinite regular language can be split by another regular language. Can every infinite context-free language be split by a regular language?
- Show there is an infinite recursive set that cannot be split by any regular language.
- Prove Schöning's result above: Every infinite recursive set can be split by a set in P.
- For a real challenge, show that there is an infinite co-r.e. set that cannot be split by any r.e. set.

*cohesive*, and r.e. sets whose complements are cohesive are called*maximal*. For question 4 you are showing that maximal sets exist, a result first proven by Friedberg in 1958.

--

Posted by Lance Fortnow to My Computational Complexity Web Log at 8/6/2003 08:59:15 AM

Powered by Blogger Pro