4 ms·
The general purpose algorithm that’s not necessarily the fastest but has an upper bound worst-case runtime: 1. Pick a paper in the field ~at random. 1b. If it
by fovc 3y ago
The general purpose algorithm that’s not necessarily the fastest but has an upper bound worst-case runtime:
1. Pick a paper in the field ~at random.
1b. If it’s basic enough for you, you’re done
2. Read the first few paragraphs and find the most basic statement that is cited
3. Find the cited paper
4. Go back to step 1b
Occasionally you’ll hit a book as the citation, in which case you must backtrack to take a different branch of the tree and try again.
In theory this is worst-case exponential, but in practice most searches end quickly
(Excuse the pun)
- pwdisswordfishc 3y agohttps://xkcd.com/559/ https://xkcd.com/559/
- fovc 3y agoI guess “pun” because I proposed an exponential worst-case but usually actually fast algorithm based on backtracking, which is what SAT is.
- eru 3y agoWhy do you backtrack when you hit a book? Btw, people often cite the earliest articles, but not necessarily the simplest. Often there are papers like '[topic] simplified' etc, and they can be quite useful. In our case, an alternative approach is to just do a web search for 'how to write a simple sat solver' and that yields eg https://www.gibiansky.com/blog/verification/writing-a-sat-solver/index.html https://www.gibiansky.com/blog/verification/writing-a-sat-so... and https://sahandsaba.com/understanding-sat-by-implementing-a-simple-sat-solver-in-python.html https://sahandsaba.com/understanding-sat-by-implementing-a-s...
- fovc 3y ago> Why do you backtrack when you hit a book? Because I usually don’t own those books and don’t have a university library > Often there are papers like '[topic] simplified' etc, and they can be quite useful. Yes! This is adding heuristics on top of the basic algorithm, of which there are many useful ones. (Figure out who the field luminaries are, what the best journals/conferences were, etc.)
- eru 3y agoYou can find many textbooks online. With varying degrees of legality.