Category: Science & Technology:Computing Theory, AI

JUDGED at 0

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

Your Buy YES Orders

Players Buying YES Coupons

Erase

Quantity

Price

Price Plot for life of 3SAT

Last trade price: 0
Current ask price: 100
Current bid price: 0
Pairs outstanding: 632
Players participating: 42 View the ticker for this Claim.

Your cash balance: 2035.91
Your holdings in this Claim: 0
Your UID:
Your password: