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 noneffective proof.
The
recursive math program tells us to ask the following
questions.

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.

If not (and the answer is NO) then is there a weaker result that is
effectively true?
Here is what is known (roughly):

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.

There is an algorithm that will, given a computable partial order of width w,
find a (5^{w}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, 6377, 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