| > ... it's basically the SAT problem. I am reminded of this classic CodeGolf.SE challenge of "P = NP" https://codegolf.stackexchange.com/a/24419 The problem was set as: > Your task is to write a program for SAT that executes in polynomial time, but may not solve all cases. To which Eric Lippert wrote: > "Appears" is unnecessary. I can write a program that really does execute in polynomial time to solve SAT problems. This is quite straightforward in fact. And has a spoiler that starts out as: > You said polynomial runtime. You said nothing about polynomial compile time. This program forces the C# compiler to try all possible type combinations for x1, x2 and x3, and choose the unique one that exhibits no type errors. The compiler does all the work, so the runtime doesn't have to. ... Unfortunately the blog post which it was linked to that went into greater detail at https://devblogs.microsoft.com/ericlippert/lambda-expression... is no longer available (even via wayback). |