Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Splitting Sets

Expand Messages
  • Lance Fortnow
    Can every infinite set in P be partitioned into two infinite subsets, each also in P? Uwe Schning answers this question in the affirmative in the Winter 1982
    Message 1 of 1 , Aug 6, 2003
    • 0 Attachment
      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:

      1. 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?
      2. Show there is an infinite recursive set that cannot be split by any regular language.
      3. Prove Schöning's result above: Every infinite recursive set can be split by a set in P.
      4. For a real challenge, show that there is an infinite co-r.e. set that cannot be split by any r.e. set.
      In recursion theory, sets that cannot be split by r.e. sets are called 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

    Your message has been successfully submitted and would be delivered to recipients shortly.