想了解一下实际工作中需要解决的 NP-complete 问题？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

想了解一下实际工作中需要解决的 NP-complete 问题？

想了解一下实际工作中需要解决的 NP-complete 问题？# Biology - 生物学

b*y2012-02-19 08:02

1 楼

【以下文字转载自 Military 讨论区】
发信人: buddyboy (hello), 信区: Military
标题: 笑死！一群老美看《人民的名义》后，畅谈观后感
发信站: BBS 未名空间站 (Tue May 2 00:45:14 2017, 美东)

k*a2012-02-19 08:02

2 楼

h*x2012-02-19 08:02

3 楼

麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
决某 NP-complete 问题的吗？
如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
谢谢！

w*t2012-02-19 08:02

4 楼

李旦还可以

l*s2012-02-19 08:02

5 楼

What is NP complete?

c*n2012-02-19 08:02

6 楼

钱不够啊，反正打酱油的

【在 k******a 的大作中提到】

: Rt

s*s2012-02-19 08:02

7 楼

你计算机版可以这么问，生物版就算做bioinformatics都不一定知道你说啥

【在 h**x 的大作中提到】

: 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
: 决某 NP-complete 问题的吗？
: 如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
: 谢谢！

h*p2012-02-19 08:02

8 楼

图个喜性呗。

h*x2012-02-19 08:02

9 楼

http://en.wikipedia.org/wiki/NP-complete
非常粗略的说，就是算法上只能做到指数级运算时间，而不是多项式运算时间
Boolean satisfiability problem (Sat.)
N-puzzle
Knapsack problem
Hamiltonian path problem
Travelling salesman problem
Subgraph isomorphism problem
Subset sum problem
Clique problem
Vertex cover problem
Independent set problem
Dominating set problem
Graph coloring problem

【在 l*********s 的大作中提到】

: What is NP complete?

w*r2012-02-19 08:02

10 楼

optimal multiple sequence alignment

【在 h**x 的大作中提到】

h*x2012-02-19 08:02

11 楼

problem size 有多大？
那你们现在是怎么算的？我主要想了解 hardware 用多大的 cluster (多少个CPU), 一
般一个问题算多少天，或多少小时？

【在 w********r 的大作中提到】

: optimal multiple sequence alignment

y*n2012-02-19 08:02

12 楼

protein folding/misfolding

y*n2012-02-19 08:02

13 楼

现在是用笨办法，两个两个去比再连起来。普通pc就能搞定还很快，效果还可以

【在 h**x 的大作中提到】

:
: problem size 有多大？
: 那你们现在是怎么算的？我主要想了解 hardware 用多大的 cluster (多少个CPU), 一
: 般一个问题算多少天，或多少小时？

j*x2012-02-19 08:02

14 楼

做bioinfor的不知道什么是NP-complete还敢称自己是做bioinfor吗，呵呵
bioinfor最初始的基本问题（例如alignment）以及至今的未解难题（例如structure
prediction）乃至当今的热点（例如network）,都是NP问题的典型

【在 s******s 的大作中提到】

: 你计算机版可以这么问，生物版就算做bioinformatics都不一定知道你说啥