k*****e
发帖数: 152 | 1 I am not good at complexity theory. If some problem is NP-complete, I know th
ere is no polynomial alg. to solve the problem. However, if some problem is N
P-hard, does it mean that there is no polynomial alg. to solve the problem? A
lso, does it mean that the problem is at least NP-complete? Thanks! | r*****y
发帖数: 507 | 2 I am not good at it too. but here is my understanding.
h
N
A
Yes.
NOT necessary bah.
【在 k*****e 的大作中提到】
: I am not good at complexity theory. If some problem is NP-complete, I know th
: ere is no polynomial alg. to solve the problem. However, if some problem is N
: P-hard, does it mean that there is no polynomial alg. to solve the problem? A
: lso, does it mean that the problem is at least NP-complete? Thanks!
| d******y
发帖数: 1039 | 3 the set of np-complete problems is a true subset of np-hard problems.
【在 r*****y 的大作中提到】
: I am not good at it too. but here is my understanding.
:
: h
: N
: A
: Yes.
: NOT necessary bah.
| k*****e
发帖数: 152 | 4 Thanks you two!
【在 d******y 的大作中提到】
: the set of np-complete problems is a true subset of np-hard problems.
| d******y
发帖数: 1039 | 5 you are welcomed.:)
【在 k*****e 的大作中提到】
: Thanks you two!
| l*****g
发帖数: 49 | 6
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
well, strictly speaking, this is true only if NP != P
most people believe that NP != P.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
here is a definition for NP-complete:
A decision problem C is NP-complete if
1. it is in NP and
2. it is NP-hard, i.e. every other problem in NP is reducible to it.
So NP-complete is a subset of NP-hard.
here is an example:
given an arbitrary graph, finding its largest clique is NP-hard;
o
【在 k*****e 的大作中提到】
: I am not good at complexity theory. If some problem is NP-complete, I know th
: ere is no polynomial alg. to solve the problem. However, if some problem is N
: P-hard, does it mean that there is no polynomial alg. to solve the problem? A
: lso, does it mean that the problem is at least NP-complete? Thanks!
|
|
