An instance of a problem for an algorithm A can be coded in
binary string of 0 and 1. Let us assume that there exists a standard
coding that is valid for this discussion. Then the set of instances
that satisfies the algorithm i.e. meets the criteria will form a
language. If A runs in polynomial-time then the language is said to in
P and set of all such languages constitutes P.
[Description is from "Introduction to Algorithm" by RivestThomas H.
Cormen, Charles E. Leiserson,
Ronald L. Rivest, Clifford Stein, 2nd Edition.]
Now it can be proved that if L1 and L2 are two languages such
that L1 and can reduces to L2 in polynomial time, then if L2 is in P
then L1 is also in P.[lemma 34.3 of the same book] Now can we prove or
disprove the following?
If L1 and L2 are two languages such that L1 can be reduced to L2 in
polynomial time, then if L1 is in P then L2 is also in P.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
