P : " This is the set of all decision problems solvable by deterministic algorithms in polynomial time "
NP: " This is the set of all decision problems solvable by non- deterministic algorithms in polynomial time "
Since Deterministic algorithms are special case of Non deterministic ones, We conclude that P C NP.
COOKS THEOREM:
Cooks theorem is better known as cooks question. Is there any single problem in NP such that if it is showed to be in P then it would imply that P=NP ? also
Satisfiability is in P iff P=NP
NP: " This is the set of all decision problems solvable by non- deterministic algorithms in polynomial time "
Since Deterministic algorithms are special case of Non deterministic ones, We conclude that P C NP.
COOKS THEOREM:
Cooks theorem is better known as cooks question. Is there any single problem in NP such that if it is showed to be in P then it would imply that P=NP ? also
Satisfiability is in P iff P=NP
No comments:
Post a Comment