[My Computational Complexity Web Log] Splitting Sets
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.
Posted by Lance Fortnow to My Computational Complexity Web Log at 8/6/2003 08:59:15 AM
Powered by Blogger Pro