steeps · HackerTrans

3 years agodiscuss

"Quantum Computing Since Democritus" mentioned in the other answer is definitely good fun, but I find it a bit tricky in places and it very much has a quantum skew. If you're after a textbook reference, then I really like Papadimitriou's Computational Complexity (no longer in print, but used copies/library copies are about) or Arora and Barak's Computational Complexity for something a bit more modern with a nice coverage.

steeps

3 years agodiscuss

One 2EXPTIME-complete problem that I really like is that of Linear Temporal Logic (LTL)[1] realizability. Informally, given a temporal logic formula over inputs and outputs, we can ask whether there exists some program which models the formula over all possible inputs.

For instance, if we label the undesirable outputs as BAD, then we can write a formula like G!BAD (read: always not BAD), and ask if there exists a program which models this formula - if there does, then we know there's some program which never enters the undesirable states, regardless of the input. You can extend this from a decision problem (yes/no answers) to synthesis, and construct such a program using similar techniques (I'm using "program" in a very specific sense here - much of the current art is focused around finite-state automata).

Shameless plug: I wrote my thesis on decision problems around the existence of game-theoretic solutions concepts (e.g. Nash equilibria, the Core) in multi-agent systems and many of these were 2EXPTIME-complete. A lot of the time you could easily show membership in 2EXPTIME by making an exponential(!) number of relevant calls to the LTL realizability problem.

[1] https://en.wikipedia.org/wiki/Linear_temporal_logic

steeps

4 years agodiscuss

Machine learning is an enormous field, and if you are after a explanation/exploration from the ground up, then Kevin Murphy's Probabilistic Machine Learning: An Introduction is very good, but a bit of a tome.

If instead, you want to focus on neural networks, I found Michael Nielsen's Neural Networks and Deep Learning an excellent resource for implementing them from first principles (available at http://neuralnetworksanddeeplearning.com/).

comments