A good algorithm will be found for the 3SAT problem, before 12/31/2020. The problem size S is the sum of the number of variables and the number of clauses. The algorithm must run in time less than 2^(S^.99) on all problems of size S, for all large S. Probabilistic algorithms are allowed, if the expected run time on each problem is less than the limit. A probabilistic algorithm must get the correct answer at least 90% of the time, and each successive run on the same problem must further decrease the probability of error by at least 50%. The algorithm must be available for public inspection 90 days prior to judging. The judge may consider empirical evidence, especially if a plausible, but unproven, algorithm is offered.
I will judge based on the wording of the claim unless it is found to be ambiguous. Such ambiguities will be resolved based on my perception of the author's intent.
A candidate algorithm must be published before the end of calendar year 2020 in a refereed journal and cited to the FX community (by mailing to fx-discuss or its equivanent) before 2021-03-01, and evidence that it satisfies the conditions of the claim must similarly be cited to the FX community before 2021-04-01.
1 @ 2 caprandom (6829) 1 @ 2 crandles (7886) 1 @ 3 Oracle (167) 1 @ 6 Oracle (167) 1 @ 9 Oracle (167) 1 @ 15 Oracle (167) 998 @ 20 tucker (303) 20 @ 25 tWD (3601) 36 @ 34 Oracle (167) 5 @ 36 Karl Hallowell (73) 1 @ 36 GTmechanic (9750) 5 @ 40 Karl Hallowell (73) 5 @ 42 Karl Hallowell (73) 10 @ 45 Karl Hallowell (73) 10 @ 49 Karl Hallowell (73) 30 @ 54 Karl Hallowell (73) 5 @ 54 CSProf (9252) 5 @ 55 CSProf (9252) 23 @ 58 happy (5591) 15 @ 58 kavi (7736) 40 @ 59 ariels (7071) 20 @ 59 Joe Taras (3191) 100 @ 60 Karl Hallowell (73) 9 @ 60 pion (5635) 5 @ 65 gmoney (3749) 5 @ 65 Corto (5007) 20 @ 70 ranchu (3586) 20 @ 70 gmoney (3749) 200 @ 75 ariels (7071) 41 @ 79 jakala (3294) 167 @ 97 Geronimo Jones (2986) 250 @ 98 Geronimo Jones (2986) 500 @ 99 Geronimo Jones (2986) 1 @ 99 crandles (7886)
