  The maximum intersection problem for a matroid and a greedoid, given by
polynomial-time oracles, is shown $NP$-hard by expressing the satisfiability of
boolean formulas in 3-conjunctive normal form as such an intersection. The
corresponding approximation problems are shown $NP$-hard for certain
approximation performance bounds. Moreover, some natural parameterized variants
of the problem are shown $W[P]$-hard. The results are in contrast with the
maximum matroid-matroid intersection which is solvable in polynomial time by an
old result of Edmonds. We also prove that it is $NP$-hard to approximate the
weighted greedoid maximization within $2^{n^{O(1)}}$ where $n$ is the size of
the domain of the greedoid.
  A preliminary version ``The Complexity of Maximum Matroid-Greedoid
Intersection'' appeared in Proc. FCT 2001, LNCS 2138, pp. 535--539,
Springer-Verlag 2001.
