Comment

Comment by pron

I take your correction re graph colouring, but the rest is pointlessly pedantic (especially "FPT in the length", which is trivial and so typically excluded from the definition).

Now, I don't know if SAT being FPT (in a parameter of interest) has anything to do with the surprising ease of many "natural" instances (even with many variables), but my point was that when many instances are easy, that doesn't mean that the class is irrelevant, it just means it's more interesting (as there's obviously a tractable subclass, albeit one we haven't yet defined succinctly).

parent pron 2 months ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton