There are all kinds of real world considerations ignored by the paper with the
"program the market” idea.
He has a vision of LaLaLand where "the market allows us to compute in
polynomial time the solution to an arbitrary 3-SAT problem”.
Perhaps he was vaguely aware that an interactive proof system is an abstract
machine that models computation as the exchange of messages between two
parties--the verifier and the prover who interact by exchanging messages to
ascertain if a given string belongs to a language or not.
There is an interactive proof for 3SAT. It requires the prover to do summations
of exponentially many terms.
A deeper understanding of 3SAT may reveal a polynomial time algorithm.
The paper is missing details but in effect he seems to suggest he wants to use
the market as an interactive proof system and to implement the simplest of all
capital-budgeting models which has just one resource constraint is called the
0–1 knapsack problem.
Industrial SAT problems have millions of variables and tens of millions of
clauses and thus the resource bottleneck is not only runtime but also storage.
Most SAT solvers include the Davis, Putnam, Logemann and Loveland algorithm DPLL
> procedure DPLL( φ, α )
>
> (SAT) (Conflict) (Unit Clause) (Pure Literal) (Branch)
>
> if φ|α is empty return SATISFIABLE
> if φ|α contains an empty clause return UNSATISFIABLE if φ|α contains a unit
> clause {p}, return DPLL( φ,αp)
> if φ|α has a pure literal p return DPLL( φ,αp)
> Let p be a literal from a minimum size clause of φ|α
> if DPLL( φ, αp ) returns SATISFIABLE
>
> return SATISFIABLE else
>
> return DPLL( φ, α¬p )
>
>
Now the CDCL (Conflict-Driven Clause Learning) approach to SAT solving is used.
Where is there anything of this nature in the description of programming the
market?
Exchanges match buy ordersor bids with sell orders or asks to execute
securities trades. In what way does throwing in some orders to the market solve
the 3SAT problem? There may be a mapping but the paper does not describe it.
If he thinks he can create zero-cost portfolios—that isn’t done in the real
world—see Regulation T.
Besides specifying a midpoint peg he doesn’t mention what information is
conveyed or inferred from market prices.about 15 thousand trades of 2.5 million
shares of 3.5 listed issues
The NYSE is handling about about 15 thousand trades of 2.5 million shares of
3.5 listed issues—if the orders placed are disruptive action would be taken
This is an NP-complete problem and so it is unlikely to find a polynomial time
algorithm for 3SAT
>
>
Donna Y
dy...@sympatico.ca
> On Sep 12, 2019, at 10:56 AM, Raul Miller <rauldmil...@gmail.com> wrote:
>
> On Wed, Sep 11, 2019 at 6:10 PM Jose Mario Quintana
> <jose.mario.quint...@gmail.com> wrote:
>> Raul also wrote:
>>> ((Honestly, though, I am surprised that you were not already aware of
>>> this aspect of SAT-3. How could SAT-3 have an equivalence to SAT-n
>>> without multiple clauses?))
>>
>> :D I do not recall stating anything about, or even mentioning, a k-SAT
>> problem, at all. Do you? I do remember quoting from the paper which
>> mentions only the 3-SAT problem; see below. (Do not blame me, I am just
>> the messenger.)
>
> Let's try this again:
>
> Let's say we've got a relatively small expression, with only 50
> variables. And, let's say we express that in terms of SAT-3, with
> three variables per clause. Do you honestly believe that there would
> only be one clause (only one order, in the market representation)? Do
> you have reason to believe that the clauses would be independent of
> each other (which would free us from regulations against
> interdependent orders)? If so, could you give an example of how this
> could work?
>
>> Is the forum's number one fan of the "Markets are efficient if and only if
>> P = NP" paper now trying to attack it? If so, then maybe this is an
>> indication that the poor dead horse has been beaten long enough.
>
> You made the claim that what you call "circuit breaker" regulations
> would not be relevant in the context of using the market as a SAT-3
> problem solver.
>
> I feel that that claim was bogus, because a typical SAT-3 expression
> will involve many interdependent clauses.
>
> ...
>
> I it's pretty clear that a SAT-3 solver involves many interdependent clauses
>
> ...
>
> Do you see why I think that this regulatory issue is significant? Do I
> need to keep restating the point until I find a way of expressing
> this, which you can understand?
>
> Or do you sincerely think that SAT-3 solvers don't involve
> interdependent clauses?
>
>> No? Then hurry up, program the market and run it, executing suitable OCO
>> orders as necessary, before the restless regulators storm TD's facilities
>> and shut down their WebBroker platform,
>
> This suggests to me that you also did not understand the reasoning
> expressed in the paper.
>
> The "program the market" idea involved a large investment and the
> payout was getting the solution to an otherwise intractable problem.
> That's only a money-maker if the intractable problem was in the way of
> achieving something valuable. But since it's exceedingly unlikely that
> the market can solve these kinds of problems, there's not much
> likelihood of getting the payout from that investment.
>
> Worse, since there are regulations (which the author of the paper
> probably wasn't aware of) which would prevent the "market programming"
> from functioning, the likelihood of payout plummets. Now, maybe -- as
> you seem to have suggested -- those regulations would not be enforced.
> That would take us from essentially no chance of payout to an
> exceedingly infinitesimal chance of payout.
>
> Thanks, but no thanks,
>
> --
> Raul
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
