一个计算生物学的 open problem，不妨想想
4. INTERVAL CUTTINGOur next problem can be easily stated without requiring any background
knowledge. The problem arises in the implementation of an algorithmic
approach for restriction mapping [6, 11]. Consider closed intervals on the
real line with integral end points. An interval [a, b] is properly contained in
another interval [c, d] if c < a <= b < d. For any interval [a, b], cutting the
interval at some point c, where a < c < b, produces two intervals [a, c]
and [c, b].
INTERVAL CUTTING
Instance: A set S of intervals.
Goal: Find the minimum number of cuts on the intervals in S so that,
in the resulting set of intervals, no interval is properly contained in any
other interval.
It is known that interval cutting has a PTAS [11]. However, we do not
know if the problem is solvable in polynomial time.
Open problem 4. Is interval cutting NP-hard?
Some more general variants of interval cutting are also studied in [11]
and some are shown to be NP-hard. 出自 [url]http://www.science.unitn.it/~rrizzi/classes/BioComp/homeworks/openProblems.pdf[/url]
上面一共有 5 个这样的 open problems，每个都以简介的数学语言描述，看上去很像 oi 题。。
页:
[1]