3 ms·
Sure, but that isn't what theory people care about. Most real world SAT instances are tractable. But SAT is still NP-Complete.
by UncleMeat 8y ago
Sure, but that isn't what theory people care about. Most real world SAT instances are tractable. But SAT is still NP-Complete.
- manifestsilence 8y agoTrue. There's sort of a divide in this thread over two questions that are interesting in completely different ways. One is how deep a game MTG is in practice, and the other is whether it is an algorithmically solvable game (no). My take-away, other than it being really cool that it's Turing-Complete, is that any bot will need to accept that not all infinities it could get stuck in are even detectable and resort to heuristics at a certain point.