Brain Food
  • Brain Food
  • pages
    • Brain Food
    • docs
      • Developer Resources
      • book-notes
        • Eloquent Javascript - Marijn Haverbeke
        • Range - David Epstein
      • computer-science
        • The Impostor's Handbook - Rob Conery
      • javascript
        • Node JS
        • You Don't Know JS Yet (2nd Edition ) - Kyle Simpson
        • react
          • React Server Components
      • reading
        • 10 Thoughts From 100 Books
      • self-development
        • Personal OKRs - 2021 (July)
      • software-development
        • Advice to Myself When Starting as a Software Developer - Gergely Orosz
        • on-software-development
        • What Silicon Valley "Gets" About Software Engineers - Gergely Orosz
      • typescript
        • TypeScript Fundamentals
      • web
        • Performance Optimization
Powered by GitBook
On this page
  • Computation
  • Complexity
  • Simple Problems (P)
  • Hard Problems (EXP)

Was this helpful?

  1. pages
  2. docs
  3. computer-science

The Impostor's Handbook - Rob Conery

Computation

What is computation? This has always been the most fundamental question of our field. In the 1930s, as the field was starting, the answer was that computation was the action of people who operated calculator machines. By the late 1940s, the answer was that computation was steps carried out by automated computers to produce definite outputs. That definition did very well: it remained the standard for nearly fifty years. But it is now being challenged. People in many fields have accepted that computational thinking is a way of approaching science and engineering. The Internet is full of servers that provide nonstop computation endlessly. Researchers in biology and physics have claimed the discovery of natural computational processes that have nothing to do with computers. How must our definition evolve to answer the challenges of brains computing, algorithms never terminating by design, computation as a natural occurrence, and computation without computers?

All these definitions frame computation as the actions of an agent carrying out computational steps. New definitions will focus on new agents: their matches to real systems, their explanatory and predictive powers, and their ability to support new designs. There have been some real surprises about what can be a computational agent and more lie ahead.

Complexity

Complexity centers around the question: how difficult is a problem to solve?

The key to Complexity Theory: you understand complexity in terms of time as you scale the inputs that go into the algorithm that you're using to solve the problem

Simple Problems (P)

T = 2x + 4y + 7

When the complexity of an algorithm scales according to a polynomial expression, we say that it scales in "P time". These are typically the simplest to work with.

Hard Problems (EXP)

T = 2^n

Hard problems are exponentially complex and take a very, very long time to solve.

Previouscomputer-scienceNextjavascript

Last updated 2 years ago

Was this helpful?