Category: Science & Technology:Computing Theory, AI

bid 0, ask 2, last 1

Owner:

0, Bank

Judge:

97, Loophole

created:

1994/11/07

due date:

2023/12/31

The Claim

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.

Judge's Statement

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.