Hi Raul & Jose Thanks for taking the trouble to point me in the right direction for understanding this EMH—N vs NP problem.
After doing some research including the knapsack problem, I re-read the paper: Markets are efficient if and only if P = NP by Philip Maymin. Initially I was confused by EMH which didn’t seem right. Then I had difficulty accepting the proof presented in the paper. Thanks to your hint about the knapsack problem, I caught up with attempts to link a proof of a specific NP-complete problem to establish a proof for the P vs NP problem. > ...envisage a situation where the values of securities depend on the > solution of instances of the 0-1 knapsack problem (KP), a combinatorial > optimization problem... (Kellerer et al., 2004 > KP is computationally hard. There is no known algorithm that both finds > the solution and is efficient, that is, can compute the solution in > polynomial time.3 Intuitively, it is “easy” to verify that a particular set > of items achieves a given total value, but it is “hard” to find the set of > items with the highest total value. > > ...[there is] a special class of problems inside NP, which are called > NP-complete problems. They are the fundamental problems to tackle in order to > solve P vs NP. We gave three examples of NP-complete problems (proof > omitted): SAT, Partition, and 3-Partition The knapsack problem KP is popular but it isn’t NP-complete and thus KP doesn’t prove whether there are solutions in P for all NP problems. > ...On the other hand, if input to the Knapsack problem is unary rather than > binary (that is, we encode a 5 as 11111), then Dynamic Programming provides a > polynomial running-time algorithm. We call such algorithms pseudo-polynomial > time algorithms. Jose said: > So far *if* the (presumably bug-free) program would fail to solve 3-SAT > problems in La La Land then some markets would not be efficient in the > strong or semi-strong sense. In other words, so far, the alleged strong or > semi-strong inefficiency *might* only be falsified in Lala Land. “Emma Stone for La La Land.” aka the briefcase problem—"It doesn’t sound very complicated, but you have to make sure you’re giving the presenter the right envelope.” Even a step-by-step simulation in La La Land will not be sufficient to settle the question. 3-SAT is N-coplete > 3-SAT: Given some boolean formula in CNF in which each clause contains 3 > literals, does it have a satisfying assignment? > Conjunctive Normal Form(CNF) > A compound statement is in conjunctive normal form if it is obtained by > operating AND among variables (negation of variables included) connected with > ORs. In terms of set operations, it is a compound statement obtained by > Intersection among variables connected with Unions. Jose said: > Maybe I am completely mistaken and you both have just shown us an > irrefutable proof that the markets are inefficient and the paper > undoubtedly proves that, > > Markets are efficient if and only if P = NP > > then you have both proved P ≠ NP; the only remaining question is how will > you both split the $1,000,000.00? >> In total, 116 of the bravest in their field have officially attempted to >> solve this mystery (though untold more computer scientists have posted >> would-be solutions to message boards and on sites like arXiv). To date, none >> of these proofs have officially been recognized by the mathematics community. arXiv is where Maymin’s paper resides—thus it is not recognized as a proof of P vs NP Grigori Perelman from Saint Petersburg successfully proved that the Poincaré conjecture is indeed true. When he was offered the £1 million prize, he declined it. He said "Everybody understood that if the proof is correct, then no other recognition is needed.” See: First Clay Mathematics Institute Millennium Prize Announced Today—March 10, 2010 Prize for Resolution of the Poincaré Conjecture a Awarded to Dr. Grigoriy Perelman First Clay Mathematics Institute Millennium Prize Announced Today Prize for Resolution of the Poincaré Conjecture a Awarded to Dr. Grigoriy Perelman https://www.claymath.org/sites/default/files/millenniumprizefull.pdf <https://www.claymath.org/sites/default/files/millenniumprizefull.pdf> Donna Y [email protected] > On Aug 30, 2019, at 9:51 AM, Jose Mario Quintana > <[email protected]> wrote: > > Donna asserted: > >>>> In mathematics, one way to disprove a theorem is to show that is leads > to a contradiction—thus the examples I mentioned that contradict EMH. > > Raul confirmed: > >>> Yes. > > I noticed: > >> Maybe I am completely mistaken and you both have just shown us an > irrefutable proof that the markets are inefficient and the paper > undoubtedly proves that, >> >> Markets are efficient if and only if P = NP >> >> then you have both proved P ≠ NP; the only remaining question is how will > you both split the $1,000,000.00? > > Just to clarify, regarding mathematical proofs, the one who puts the last > piece of the puzzle in place gets the credit. No worries though, I think, > as Perelman does as well, that this is a simpleminded custom and following > his lead, I would decline the prize. The $1M is all yours to enjoy. > > > > On Sun, Aug 25, 2019 at 4:59 PM Jose Mario Quintana < > [email protected]> wrote: >> >> >>>> Jose makes a good point though—if the author was trying to disprove >>>> efficient market hypothesis—then proving the weakest form to be false >>>> implies all forms are false. >>> >>> But, technically, the author didn't prove EMH false -- he outlined an >>> equivalence between EMH and the knapsack problem. >> >> If one can show that the markets are probably not weak efficient then one > can state that "the markets are probably not efficient" (in any form) as > the author states in the abstract of his paper. >> >>> In other words if we could solve problems whose complexity grows >>> exponentially, then EMH would be true. Since we can't, we can at least >>> classify EMH as not always being useful in the general case. >> >> Clarify why "Since we can't," then "we can at least classify EMH as not > always being useful in the general case" and what your statement means, in > particular, "being useful" (if you can). >> >>> Actually, he was talking about offering contract terms whose conditions >>> would be met by the problem solution. >>> >>> But his point was that it's not reasonable to expect that the market > would >>> be able to solve such things. >>> >> >> So far *if* the (presumably bug-free) program would fail to solve 3-SAT > problems in La La Land then some markets would not be efficient in the > strong or semi-strong sense. In other words, so far, the alleged strong or > semi-strong inefficiency *might* only be falsified in Lala Land. >> >>>> In mathematics, one way to disprove a theorem is to show that is > leads to a contradiction—thus the examples I mentioned that contradict EMH. >> >>> >>> Yes. >> >> Maybe I am completely mistaken and you both have just shown us an > irrefutable proof that the markets are inefficient and the paper > undoubtedly proves that, >> >> Markets are efficient if and only if P = NP >> >> then you have both proved P ≠ NP; the only remaining question is how will > you both split the $1,000,000.00? >> >> >> > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
