Processing math: 72%
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
Dadidadida ...
Links
My Profile
Ryan's Blog
Ryan's Homework
Beanlib
Previous Posts
Clique, Independent Set and Vertex Cover
φ
(
1
)
=
1
Ex 2.36
(n-1)! \equiv -1 \pmod n
Ex 2.35 Square roots of
1 \pmod {2^x}
Ex 2.34 Euler's criterion
Ex 2.33
(\mathbb{Z_n^*})^m
On Thue's Lemma
Attempt of an alternative proof of the Product Rule
Ex 2.26
Z_{19}^*
and multiplicative order 18
Ex 2.25
\varphi_2(n)
Archives
03/01/2005 - 04/01/2005
06/01/2005 - 07/01/2005
07/01/2005 - 08/01/2005
08/01/2005 - 09/01/2005
09/01/2005 - 10/01/2005
10/01/2005 - 11/01/2005
11/01/2005 - 12/01/2005
12/01/2005 - 01/01/2006
01/01/2006 - 02/01/2006
02/01/2006 - 03/01/2006
03/01/2006 - 04/01/2006
04/01/2006 - 05/01/2006
05/01/2006 - 06/01/2006
06/01/2006 - 07/01/2006
07/01/2006 - 08/01/2006
08/01/2006 - 09/01/2006
09/01/2006 - 10/01/2006
10/01/2006 - 11/01/2006
12/01/2006 - 01/01/2007
03/01/2007 - 04/01/2007
04/01/2007 - 05/01/2007
05/01/2007 - 06/01/2007
06/01/2007 - 07/01/2007
07/01/2007 - 08/01/2007
09/01/2007 - 10/01/2007
10/01/2007 - 11/01/2007
12/01/2007 - 01/01/2008
01/01/2008 - 02/01/2008
02/01/2008 - 03/01/2008
04/01/2008 - 05/01/2008
07/01/2008 - 08/01/2008
08/01/2008 - 09/01/2008
09/01/2008 - 10/01/2008
11/01/2008 - 12/01/2008
04/01/2009 - 05/01/2009
09/01/2009 - 10/01/2009
10/01/2009 - 11/01/2009
11/01/2009 - 12/01/2009
02/01/2010 - 03/01/2010
03/01/2010 - 04/01/2010
08/01/2010 - 09/01/2010
09/01/2010 - 10/01/2010
06/01/2011 - 07/01/2011
10/01/2011 - 11/01/2011
11/01/2011 - 12/01/2011
01/01/2012 - 02/01/2012
02/01/2012 - 03/01/2012
03/01/2012 - 04/01/2012
04/01/2012 - 05/01/2012
05/01/2012 - 06/01/2012
06/01/2012 - 07/01/2012
08/01/2012 - 09/01/2012
09/01/2012 - 10/01/2012
10/01/2012 - 11/01/2012
11/01/2012 - 12/01/2012
12/01/2012 - 01/01/2013
01/01/2013 - 02/01/2013
02/01/2013 - 03/01/2013
03/01/2013 - 04/01/2013
04/01/2013 - 05/01/2013
05/01/2013 - 06/01/2013
06/01/2013 - 07/01/2013
07/01/2013 - 08/01/2013
08/01/2013 - 09/01/2013
10/01/2013 - 11/01/2013
11/01/2013 - 12/01/2013
12/01/2013 - 01/01/2014
01/01/2014 - 02/01/2014
02/01/2014 - 03/01/2014
03/01/2014 - 04/01/2014
04/01/2014 - 05/01/2014
05/01/2014 - 06/01/2014
06/01/2014 - 07/01/2014
07/01/2014 - 08/01/2014
10/01/2014 - 11/01/2014
04/01/2015 - 05/01/2015
09/01/2018 - 10/01/2018
11/01/2018 - 12/01/2018
12/01/2018 - 01/01/2019
04/01/2019 - 05/01/2019
12/01/2019 - 01/01/2020
