Google
 
Web unafbapune.blogspot.com

Sunday, February 10, 2013

 

Polynomial Time Reduction from \(X\) to \(Y\)

Reducing a problem \(X\) to a problem \(Y\) implies:

\(X\) is at least as hard to solve as \(Y\)
\(Y\) is at least as hard to solve as \(X\)
If \(X\) can be solved in polynomial time, then so can \(Y\)
If \(Y\) can be solved in polynomial time, then so can \(X\)

What do you think ?

See Unit 2.3 at Intro to Theoretical Computer Science.


# posted by rot13(Unafba Pune) @ 12:45 PM
Comments: Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?