News for hackers. Stuff that matters.

steeps

Re:Problems harder than NP-Complete on Friday May 12, 2023 @07:10AM (#35914571)
"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.
Re:Problems harder than NP-Complete on Thursday May 11, 2023 @07:07PM (#35909543)
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

Re:Ask HN: Tutorials Written with Heavy Dependencies on Thursday December 29, 2022 @06:04PM (#34179314)
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, available at http://neuralnetworksanddeeplearning.com/, an excellent resource for implementing them from first principles.

Re:Why are some egg yolks so orange? on Sunday April 17, 2022 @06:36AM (#31059893)
J. Kenji López-Alt has a bit in his Food Lab book where he explores the effect of yolk colour on taste. Paraphrasing, the takeaway is that people generally perceive redder/deeper yolks as more flavoursome, but if you remove this factor (with food colouring, say), then people can't tell the difference. He summarises this in a twitter thread: [1]

[1]: https://nitter.net/kenjilopezalt/status/1176542696724320256

Re:A Reckless Guide to OpenBSD on Thursday February 17, 2022 @04:31AM (#30371198)
Fear not, the website has a theme selector: https://www.exoticsilicon.com/themes. I quite like the 1980s theme.
Re:Stop paying DocuSign $2 for an e-signature on Wednesday November 17, 2021 @01:22PM (#29256780)
What benefits do products such as DocuSign or cheapesignature have over digital signatures provided by open source libraries such as NaCl [1]?

[1] https://nacl.cr.yp.to/