NP

[Yiyao LIU]

If a problem in NP can be solved in polynomial time, then all problems
in NP can be solved in polynomial time.
Is this correct?
According to my understanding in the lecture, it should be.
However, there's some online material indicating it's wrong.

So, if it's wrong, why?

[Eli Spiro]

My understanding is that if we could find a polynomial time solution to an *NP-complete* problem, then all problems in NP could be solved in polynomial time, and then we would have P=NP.

We already have polynomial time solutions to some problems in NP, since every problem in P is also in NP.

[Jayson Rhynas]

Post by Yiyao LIU
If a problem in NP can be solved in polynomial time, then all problems
in NP can be solved in polynomial time.
Is this correct?
According to my understanding in the lecture, it should be.
However, there's some online material indicating it's wrong.
So, if it's wrong, why?

If what you said was true, then we could show that P=NP, since you're
basically saying NP is a subset of (or equal to P), and we already know
P is a subset of (or equal to ) NP.
What the lectures/slides actually say is if every program in NP can be
reduced to a given program Q, then Q is in NP-hard. Q may or may not be
in NP.

[Mike D'Anna]

Post by Jayson Rhynas

Post by Yiyao LIU
If a problem in NP can be solved in polynomial time, then all problems
in NP can be solved in polynomial time.
Is this correct?
According to my understanding in the lecture, it should be.
However, there's some online material indicating it's wrong.
So, if it's wrong, why?

If what you said was true, then we could show that P=NP, since you're
basically saying NP is a subset of (or equal to P), and we already know
P is a subset of (or equal to ) NP.
What the lectures/slides actually say is if every program in NP can be
reduced to a given program Q, then Q is in NP-hard. Q may or may not be
in NP.

...

P is a subset of NP. If we could prove that an NP-Hard problem can be
done in P time, then P=NP. However there are some NP problems that are
not NP-Hard.

The set of NP problems that are also NP hard are called NP-Complete.
These are the problems the notes are referring to.

Note that there's also some NP-Hard problems that are not in NP, but I
don't believe we're required to know about them (they're neat, though).

Did that make sense?

-Mike

[Yiyao LIU]

On Dec 15, 6:09 pm, Mike D'Anna

Post by Mike D'Anna

Post by Jayson Rhynas

Post by Yiyao LIU
If a problem in NP can be solved in polynomial time, then all problems
in NP can be solved in polynomial time.
Is this correct?
According to my understanding in the lecture, it should be.
However, there's some online material indicating it's wrong.
So, if it's wrong, why?

If what you said was true, then we could show that P=NP, since you're
basically saying NP is a subset of (or equal to P), and we already know
P is a subset of (or equal to ) NP.
What the lectures/slides actually say is if every program in NP can be
reduced to a given program Q, then Q is in NP-hard. Q may or may not be
in NP.

P is a subset of NP. If we could prove that an NP-Hard problem can be
done in P time, then P=NP. However there are some NP problems that are
not NP-Hard.
The set of NP problems that are also NP hard are called NP-Complete.
These are the problems the notes are referring to.
Note that there's also some NP-Hard problems that are not in NP, but I
don't believe we're required to know about them (they're neat, though).
Did that make sense?
-Mike

...

cool, thanks for ur explanation.
I mixed NP and NP-complete XD