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

[Computational Complexity] When to declare a problem is hard?/Constructive ve...

Expand Messages
  • GASARCH
    Why do we think solving P vs NP is hard? There are some matematical reasons (oracles, Natural Proofs, Algebraization) but there is also this notion that many
    Message 1 of 1 , Jan 30, 2009
    • 0 Attachment
      Why do we think solving P vs NP is hard? There are some matematical reasons (oracles, Natural Proofs, Algebraization) but there is also this notion that many smart peoplet of people have worked on it.

      If there is an open problem that not that many people have worked on, even if they are brilliant people, its hard to know how hard it is. I present an open problem of this nature.

      Recall Dilworths theorem: If P is a partial order of width w (so the largest set of inc elements has w elements) then there exists w chains that cover P (there are w disjoint linear suborders of P that contain all of P). Dilworths theorem: If P is a partial order of width w (so the largest set of inc elements has w elements) then there exists w chains that cover P (there are w disjoint linear suborders of P that contain all of P). Dilworths theorem: If P is a partial order of width w (so the largest set of inc elements has w elements) then there exists w chains that cover P (there are w disjoint linear suborders of P that contain all of P).

      Dilworths theorem is usually proven for the finite case and then, by the usual compactness arguments, holds for the infinite case. So the infinite case has a non-effective proof. The recursive math program tells us to ask the following questions.
      1. Is there a computable function that will, given the Turing machine for a partial order on the set N (input (x,y), output 1 if x&le y, 2 if y &le x, 3 if x and y are incomparable) and given the width w, output a set of w total Turing machines that decide w disjoint chains that cover the partial order.
      2. If not (and the answer is NO) then is there a weaker result that is effectively true?
      Here is what is known (roughly):
      1. For every w there is a computable partial order of width w that cannot be covered with ((w+1) choose 2)-1 recursive chains (it can be covered with ((w+1) choose 2) recursive chains). Proven by Szemeredi and Trotter but reported in Recursive Ordered Sets by Henry A. Kierstead, In the book Combinatorics and Ordered Sets. American Mathematical Society, 1986. The proof can also be found in my survey of recursive combinatorics.
      2. There is an algorithm that will, given a computable partial order of width w, find a (5w-1)/4 computable chains that cover it. (An effective version of {D}ilworth's Theorem by Henry A. Kierstead. Transactions of the American Math Society, vol 268, 63--77, 1981.)
      The open problem is to CLOSE THAT GAP! How hard is this? I've asked around and it seems that while Hal Kierstead is a brilliant guy and he's had a few brilliant people have working on it, it remains uncracked. Does this mean its hard? Not necc. No matter how Brilliant the people working on it are, I think you need to have a community of people working on a problem for a number of years before you can say WOW, thats a hard problem!.

      --
      Posted By GASARCH to Computational Complexity at 1/30/2009 11:35:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.