FX Home
 
Claims
All Accounts
Ticker
Summary
Mailing Lists

Your Account
Your Profile

Help

Contact Us
Tip

Claim 3SAT - Good 3SAT Algorithm by 2020

Category: Science & Technology:Computing Theory, AI bid 0, ask 1, 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.

The Market

Price Plot for life of 3SAT
Your UID:
Your password: