The Stack Overflow podcast is back! Listen to an interview with our new CEO.

New answers tagged


Wolfram's rule 30 is a one dimensional cellular automaton. If you want to know the state of the CA at step $t$, given the initial configuration, you just need to run the rule for $t$ steps. At every step the computation consist in no more than a bunch of if's, so the time complexity of such CA is linear in $t$.


Polynomial reduction and certificates have very little to do with each other. Basically, we defined the set P of all easy problems that can be solved by a computer in polynomial time. Then obviously problems not in P are hard. We then defined the set NP of all problems which can be solved in polynomial time by a non-deterministic computer, in other ...

Top 50 recent answers are included