Computational Complexity Quotes

Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.

Computer science is not as old as physics; it lags by a couple of hundred years. However, this does not mean that there is significantly less on the computer scientist's plate than on the physicist's: younger it may be, but it has had a far more intense upbringing!

The computer is not, in our opinion, a good model of the mind, but it is as the trumpet is to the orchestra - you really need it. And so, we have very massive simulations in computers because the problem is, of course, very complex.

[Computer science] is not really about computers and it's not about computers in the same sense that physics is not really about particle accelerators, and biology is not about microscopes and Petri dishes... and geometry isn't really about using surveying instruments.

The underlying physical laws necessary for the mathematical theory of a large part of physics and the whole of chemistry are thus completely known, and the difficulty is only that the exact application of these laws leads to equations much too complicated to be soluble. It therefore becomes desirable that approximate practical methods of applying quantum mechanics should be developed, which can lead to an explanation of the main features of complex atomic systems without too much computation.

Formula creation is magnitudes harder for computer algorithms than actually executing within a formula. But once the genre is created and the formula is known, then the computer can do the repetitive task of executing within the genre.

A state-of-the-art calculation requires 100 hours of CPU time on the state-of-the-art computer, independent of the decade.

It would be very discouraging if somewhere down the line you could ask a computer if the Riemann hypothesis is correct and it said, 'Yes, it is true, but you won't be able to understand the proof.'

One can think of any given axiom system as being like a computer with a certain limited amount of memory or processing power. One could switch to a computer with even more storage, but no matter how large an amount of storage space the computer has, there will still exist some tasks that are beyond its ability.

A formula can be very simple, and create a universe of bottomless complexity.

In enabling mechanism to combine together general symbols in successions of unlimited variety and extent, a uniting link is established between the operations of matter and the abstract mental processes of the most abstract branch of mathematical science.

Now, the reason that we think computer science is about computers is pretty much the same reason that the Egyptians thought geometry was about surveying instruments. And that is, when some field is just getting started and you don't really understand it very well, it's very easy to confuse the essence of what you're doing with the tools that you use.

The question you raise, 'How can such a formulation lead to computations?' doesn't bother me in the least! Throughout my whole life as a mathematician, the possibility of making explicit, elegant computations has always come out by itself, as a byproduct of a thorough conceptual understanding of what was going on. Thus I never bothered about whether what would come out would be suitable for this or that, but just tried to understand - and it always turned out that understanding was all that mattered.

In a world in which the price of calculation continues to decrease rapidly, but the price of theorem proving continues to hold steady or increase, elementary economics indicates that we ought to spend a larger and larger fraction of our time on calculation.

The primary consequence of the computational nature of the universe is that the universe naturally generates complex systems, such as life. Although the basic laws of physics are comparatively simple in form, they give rise, because they are computationally universal, to systems of enormous complexity.

Because of the Turing completeness theory, everything one Turing-complete language can do can theoretically be done by another Turing-complete language, but at a different cost. You can do everything in assembler, but no one wants to program in assembler anymore.

My father taught me Basic and rudimentary C, I learned everything else on my own, including studying computational complexity on my own. That's more a function of my age than anything else though - back when I was in school there were hardly any programming classes.

The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers.

I take the view that we all have permission to be a little baffled by quantum information science and algorithmic information theory.

My work was fairly theoretical. It was in recursive function theory. And in particular, hierarchies of functions in terms of computational complexity. I got involved in real computers and programming mainly by being - well, I was interested even as I came to graduate school.

The confusion, the difficulties, the contradictions which, in consequence of a want of accurate distinctions in this particular, have up to even a recent period encumbered mathematics in all those branches involving the consideration of negative and impossible quantities, will at once occur to the reader who is at all versed in this science, and would alone suffice to justify dwelling somewhat on the point, in connexion with any subject so peculiarly fitted to give forcible illustration of it as the Analytical Engine.

There's a good part of Computer Science that's like magic. Unfortunately there's a bad part of Computer Science that's like religion.

I would suggest, merely as a metaphor here, but also as the basis for a scientific program to investigate the computational capacity of the universe, that this is also a reasonable explanation for why the universe is complex.

Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack.