New answers tagged polynomial-time
1
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$.
0
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
