Dr. Volkan Tunalı's Personal Blog

Computer, Technology, Science, Art

Archive for the ‘computing’ tag

Storage Cost over Years

leave a comment

Every time I buy a new PC, either desktop or notebook, its hard disk capacity is larger than the previous one even though the total price of the PC is about equal. The same thing may apply for the other components of the PC like main memory capacity and CPU power, but hard disk capacity is something very different.

Matthew Komorowski has collected hard drive capacity/price data and created the graph below:

Storage cost over years
Source: http://www.mkomo.com/cost-per-gigabyte

Komorowski has also drawn a conclusion about the capacity/cost trend as:

Over the last 30 years, space per unit cost has doubled roughly every 14 months (increasing by an order of magnitude every 48 months)

Moreover, he has a formula for the cost as

cost = 10-0.2502(year-1980)+6.304

Below are two pictures from computer magazines of 80s. Incredible!

Written by Volkan TUNALI

September 18th, 2010 at 12:24 pm

Proof that P is not Equal to NP?

one comment

Complexity ClassesFor a few days, everyone in the field of computer science has been talking about the manuscript P ≠ NP published by Vinay Deolalikar from HP Research Labs on August 6, 2010. The 102-page manuscript on the P versus NP problem has taken so much attention from computer science researchers like Scott Aaronson, Greg Baker, and Dick Lipton.

Let’s see what Wikipedia says about P ≠ NP as a refreshment for the subject:

The relationship between the complexity classes P (Polynomial time) and NP (Nondeterministic Polynomial time) is an unsolved problem in theoretical computer science, and is considered by many theoretical computer scientists to be the most important problem in the field.

A proof that showed that P ≠ NP, while lacking the practical computational benefits of a proof that P = NP, would also represent a very significant advance in computational complexity theory and provide guidance for future research. It would allow one to show in a formal way that many common problems cannot be solved efficiently, so that the attention of researchers can be focused on partial solutions or solutions to other problems. Due to widespread belief in P ≠ NP, much of this focusing of research has already taken place.

Yes, P ≠ NP is the expected answer, yet there is no accepted proof for that. It will be very interesting and lucky for us to witness an important milestone in computer science if Deolalikar’s claimed proof is found correct and approved by the computer science community. I think acceptance or rejection will take some time, and I’ll be waiting impatiently.

Update Jan 20th, 2011: Today I’ve seen a new work that claims P = NP with a Polynomial Algorithm for Boolean 3-Satisfiability Problem by Vladimir Romanov. http://romvf.wordpress.com/2011/01/19/open-letter/

Written by Volkan TUNALI

August 9th, 2010 at 5:45 pm