Programming stuff

Sunday, November 29, 2009

Computational Complexity and Quantum Compuation

Cool some more video's I probably don't have time to watch but interesting nonetheless!
Computational complexity is the study of what resources, such as time and memory, are needed to carry out given computational tasks, with a particular focus on lower bounds for the amount needed of these resources. Proving any result of this kind is notoriously difficult, and includes the famous problem of whether P = N P . This course will be focused on two major results in the area. The first is a lower bound, due to Razborov, for the number of steps needed to determine whether a graph contains a large clique, if only “monotone” computations are allowed. This is perhaps the strongest result in the direction of showing that P and N P are distinct (though there is unfortunately a very precise sense in which the proof cannot be developed to a proof of the whole conjecture). The second is Peter Shor’s remarkable result that a quantum computer can factorize large integers in
polynomial time
Posted by daveangel at 2:32 AM

No comments:

Post a Comment

Newer Post Older Post Home
Subscribe to: Post Comments (Atom)

About Me

daveangel
PC and Apple computer programmer with focus on security tech.
View my complete profile

Blog Archive

  • ►  2011 (40)
    • ►  October (1)
    • ►  August (28)
    • ►  July (8)
    • ►  February (1)
    • ►  January (2)
  • ►  2010 (18)
    • ►  June (4)
    • ►  March (2)
    • ►  February (11)
    • ►  January (1)
  • ▼  2009 (34)
    • ►  December (3)
    • ▼  November (11)
      • Computational Complexity and Quantum Compuation
      • Mathematicians Prove Tetris Is Tough
      • Apple job of the day
      • Am I In the Wrong Degree Program?
      • Google's Go
      • Finding shortest path
      • 13 Tools for Building Your Own iPhone App
      • Visual Studio 2008 for Gaming: Developing 3D Games
      • What Every Computer Scientist Should Know About Fl...
      • PowerShellPack
      • Game Programming with Silverlight
    • ►  October (16)
    • ►  September (4)
  • ►  2008 (1)
    • ►  January (1)
  • ►  2007 (5)
    • ►  July (1)
    • ►  April (1)
    • ►  March (3)
Awesome Inc. theme. Powered by Blogger.