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

Your Buy YES Orders Players Buying YES Coupons
EraseQuantityPrice
     
Price Plot for life of 3SAT
Last trade price: 1
Current ask price: 1
Current bid price: 0
Pairs outstanding: 632
Players participating: 42
View the ticker for this Claim.

Your cash balance: 6418.22
Your holdings in this Claim: -2
Your UID:
Your password:
Your Sell YES Orders Players Selling YES Coupons
EraseQuantityPrice
     1 @ 1   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)
     

Back to my account page.