h**x
发帖数: 34 | 1 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
决某 NP-complete 问题的吗？
如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
谢谢！ |
l*********s
发帖数: 5409 | |
s******s
发帖数: 13035 | 3 你计算机版可以这么问，生物版就算做bioinformatics都不一定知道你说啥
【在 h**x 的大作中提到】
: 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
: 决某 NP-complete 问题的吗？
: 如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
: 谢谢！
|
h**x
发帖数: 34 | 4
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********r
发帖数: 9 | 5 optimal multiple sequence alignment
【在 h**x 的大作中提到】
: 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
: 决某 NP-complete 问题的吗？
: 如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
: 谢谢！
|
h**x
发帖数: 34 | 6
problem size 有多大？
那你们现在是怎么算的？我主要想了解 hardware 用多大的 cluster (多少个CPU), 一
般一个问题算多少天，或多少小时？
【在 w********r 的大作中提到】
: optimal multiple sequence alignment
|
y**********n
发帖数: 478 | 7 protein folding/misfolding |
y**********n
发帖数: 478 | 8 现在是用笨办法，两个两个去比再连起来。普通pc就能搞定还很快，效果还可以
【在 h**x 的大作中提到】
:
: problem size 有多大？
: 那你们现在是怎么算的？我主要想了解 hardware 用多大的 cluster (多少个CPU), 一
: 般一个问题算多少天，或多少小时？
|
j****x
发帖数: 1704 | 9 做bioinfor的不知道什么是NP-complete还敢称自己是做bioinfor吗，呵呵
bioinfor最初始的基本问题（例如alignment）以及至今的未解难题（例如structure
prediction）乃至当今的热点（例如network）,都是NP问题的典型
【在 s******s 的大作中提到】
: 你计算机版可以这么问，生物版就算做bioinformatics都不一定知道你说啥
|
l**********1
发帖数: 5204 | 10 PRH to target DNA
protein oligomeric assembly
//www.ncbi.nlm.nih.gov/pubmed/20675722
【在 h**x 的大作中提到】
:
: problem size 有多大？
: 那你们现在是怎么算的？我主要想了解 hardware 用多大的 cluster (多少个CPU), 一
: 般一个问题算多少天，或多少小时？
|
