Posts

Showing posts from September, 2017

The NP vs P issue

Image
By McDonald, T. | Last updated: 7/9/2017 We face problems every day; subsequently, we spend a lot of time attempting to find a reasonable solution even if we do not realise it.  Solving problems is a big part of computer science.  In fact, problems are so important that computer science separates them into different classes including P, NP, NP-complete and NP-hard, but what does it all mean and can NP =P? Computer scientists have developed a way of measuring how long it takes to compute a problem. This is not as easy as it sounds since we cannot just time how long it takes.  Think about it for a minute, if timing an algorithm by looking at the clock, the timing run on different computers would be different each time because different computers could have different hardware such as processors and memory.  Even if running the same algorithm several times on the same computer, the time spent running the algorithm would depend on the other operations the computer was running

Is everything computable?

Image
By McDonald, T. | Last updated 30th of November   Do you think your computer is amazing? It can do so much and reasonably quick most of the time, yes?  Perhaps you are beginning to think it will not be long before a computer can accomplish any task especially with knowledge of Moore’s law whereby the number of transistors per square inch on an integrated circuit doubles every eighteen months.  Nevertheless, some problems are not just difficult they are impossible to solve. For some problem to be computable, it would need to be possible to solve it in a finite number of steps for every instance of that problem; we call this effective procedure.  Alan Turing came up with the idea of a machine that could solve a problem if given a set of precise instructions called a program, which he called a Turing machine.  In addition, he theorised of a universal Turing machine that could take the state of any other Turing machine.  It is important to remember that at the time, modern day co