Web
unafbapune.blogspot.com
Saturday, February 16, 2013
P vs NP
P = NP would mean every computational problem can be solved in polynomial time.
P \(\ne\) NP would mean no NP-complete problems could be solved in polynomial time.
There are NP-complete problems that are "easier" to solve in practice than others.
The ability to solve some instances of an NP-complete problem implies P = NP.
Showing a problem is NP-complete means it can't be solved in polynomial.
Which one(s) of the above are true ?
See Problem Set 2 at
Intro to Theoretical Computer Science
.
#
posted by rot13(Unafba Pune) @ 1:07 PM
Comments:
Post a Comment
<< Home
Dadidadida ...
Links
My Profile
Ryan's Blog
Ryan's Homework
Beanlib
Previous Posts
Only Solvable in Exponential Time
Which distributions ?
Line Rotation
Trig Function Derivatives
Polynomial Time Reduction from \(X\) to \(Y\)
Clique, Independent Set and Vertex Cover
\(\varphi(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
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
