Bitcoin Forum
June 22, 2024, 10:32:34 PM *
News: Voting for pizza day contest
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Markets are efficient if and only if P = NP  (Read 1753 times)
herzmeister (OP)
Legendary
*
Offline Offline

Activity: 1764
Merit: 1007



View Profile WWW
May 21, 2013, 10:25:34 PM
 #1

Worth a discussion or two.  Smiley

http://arxiv.org/abs/1002.2284v2

Quote
I prove that if markets are weak-form efficient, meaning current prices fully reflect all information available in past prices, then P = NP, meaning every computational problem whose solution can be verified in polynomial time can also be solved in polynomial time. I also prove the converse by showing how we can "program" the market to solve NP-complete problems. Since P probably does not equal NP, markets are probably not efficient. Specifically, markets become increasingly inefficient as the time series lengthens or becomes more frequent. An illustration by way of partitioning the excess returns to momentum strategies based on data availability confirms this prediction.


https://localbitcoins.com/?ch=80k | BTC: 1LJvmd1iLi199eY7EVKtNQRW3LqZi8ZmmB
townf
Newbie
*
Offline Offline

Activity: 42
Merit: 0


View Profile
May 21, 2013, 10:49:07 PM
 #2

Can you dumb that down for me
townf
Newbie
*
Offline Offline

Activity: 42
Merit: 0


View Profile
May 21, 2013, 10:50:19 PM
 #3

Pretend that my IQ is just in the 100's
notme
Legendary
*
Offline Offline

Activity: 1904
Merit: 1002


View Profile
May 21, 2013, 11:18:58 PM
 #4

This paper will not be accessible to you if you aren't familiar with formal mathematics and computational complexity theory.

TL;DR: Either economists are wrong about their efficient market hypothesis, or computers have a shitload of computational ability that computer scientists just haven't been clever enough to exploit yet.

https://www.bitcoin.org/bitcoin.pdf
While no idea is perfect, some ideas are useful.
townf
Newbie
*
Offline Offline

Activity: 42
Merit: 0


View Profile
May 21, 2013, 11:30:18 PM
 #5

This paper will not be accessible to you if you aren't familiar with formal mathematics and computational complexity theory.

TL;DR: Either economists are wrong about their efficient market hypothesis, or computers have a shitload of computational ability that computer scientists just haven't been clever enough to exploit yet.

As long i can still gits my DrUgZez with them ther bzitk01nz, sall good dawg. Word
notme
Legendary
*
Offline Offline

Activity: 1904
Merit: 1002


View Profile
May 21, 2013, 11:49:44 PM
 #6

This paper will not be accessible to you if you aren't familiar with formal mathematics and computational complexity theory.

TL;DR: Either economists are wrong about their efficient market hypothesis, or computers have a shitload of computational ability that computer scientists just haven't been clever enough to exploit yet.

As long i can still gits my DrUgZez with them ther bzitk01nz, sall good dawg. Word

Way to represent the community Roll Eyes.

https://www.bitcoin.org/bitcoin.pdf
While no idea is perfect, some ideas are useful.
Seal
Donator
Hero Member
*
Offline Offline

Activity: 848
Merit: 1078


View Profile WWW
May 22, 2013, 12:09:27 PM
 #7

This paper will not be accessible to you if you aren't familiar with formal mathematics and computational complexity theory.

TL;DR: Either economists are wrong about their efficient market hypothesis, or computers have a shitload of computational ability that computer scientists just haven't been clever enough to exploit yet.

As long i can still gits my DrUgZez with them ther bzitk01nz, sall good dawg. Word

Way to represent the community Roll Eyes.

Lol, i totally don't get this at all.

DefiDive - Filter the noise
A clean crypto asset management terminal
caveden
Legendary
*
Offline Offline

Activity: 1106
Merit: 1004



View Profile
May 22, 2013, 12:20:53 PM
 #8

Either economists are wrong about their efficient market hypothesis

This hypothesis doesn't come from those who practice economics they way it should be, i.e., aprioristically. They are commonly called "Austrian economists" or economists of the Austrian School, since the first members of these school of economics were Austrians.
A quick search found me this article from Tom Woods: https://mises.org/daily/4904/Following-the-EfficientMarkets-Hypothesis-into-Absurdity (haven't read it entirely though, just linking it here to make it explicit that actual economists don't agree with this theory)
aigeezer
Legendary
*
Offline Offline

Activity: 1450
Merit: 1013


Cryptanalyst castrated by his government, 1952


View Profile
May 22, 2013, 01:09:05 PM
 #9

Assuming that the author's proof is valid (I haven't checked), the important part would be: "Since P probably does not equal NP, markets are probably not efficient."

It is close to certain that P is not equal to NP - the author's "probably" is an understatement.

I used to know this stuff pretty well. It was a big deal in grad school, but that was a long time ago. Here's what I remember, with apologies to anyone who is really up on this stuff.

Mathematicians have been looking at this issue closely for generations. The basic issue is whether "nondeterministic" (massively parallel, well - infinitely parallel if you want to get picky) problem solving approaches can "break through" to solve very difficult problems of the type that get much harder as the size of the data set increases. Generally, problems that can be dealt with in "polynomial time" are considered tractable, say where the difficulty can be expressed with a formula such as 100 times n-cubed + 53 n-squared + some constant, where n is the size of the problem space. However, problems where n appears in an exponent are considered intractable - the difficulty increases so rapidly as the size of the data set increases, that they in effect cannot be solved by any known method. They might be easily solved where n is a small number but the issue comes into play as the data set size increases.

To dip a bit deeper...

Suppose the problem at hand is to print "all" the prime numbers. A deterministic computer would use an algorithm such as the Sieve of Eratoshenes, calculate a prime, print it, calculate the next prime, rinse and repeat forever - an intractable problem. A nondeterministic computer could "magically" have "all" the primes available, ready for printing, but the problem would still be intractable because the print job would still never end - still intractable even though the hardest part (calculating the primes) seems to have been magically resolved.

The academic issue is whether the "problem space" for deterministic problems is the same as for nondeterministic ones. Does P=NP? Is it possible that we just haven't found the right way of looking at the two spaces yet, and that some day someone might prove that they are equivalent. It would be a VERY big deal if that happened (all NP problems are mathematically equivalent, so proof for one would be proof for all), but it seems extremely unlikely by now.

Anyway, the takeaway on the original paper is still just "markets are probably not efficient" (if the author's math is sound).

benjamindees
Legendary
*
Offline Offline

Activity: 1330
Merit: 1000


View Profile
May 22, 2013, 01:46:39 PM
 #10

This is an obvious conclusion.  Nothing is perfectly efficient.  Free markets that account for negative externalities tend towards efficiency, while centrally-planned economies tend towards chaos and collapse.

Civil Liberty Through Complex Mathematics
aigeezer
Legendary
*
Offline Offline

Activity: 1450
Merit: 1013


Cryptanalyst castrated by his government, 1952


View Profile
May 22, 2013, 02:40:56 PM
 #11

This is an obvious conclusion.  Nothing is perfectly efficient.  Free markets that account for negative externalities tend towards efficiency, while centrally-planned economies tend towards chaos and collapse.

Beware of "obvious conclusions". It is perfectly obvious that the earth is flat if you look out your window.      Smiley

Anyway, obvious or not, the "efficient market hypothesis" is a widely held view in economics and the exposition of it is much more subtle than "perfect efficiency". I happen to think it is false, but thinking something and proving it are two different things. The point of the article under discussion is that the author claims to have proof that markets are not efficient.

Wiki backgrounder on the efficient market hypothesis if you're interested in the gory details: http://en.wikipedia.org/wiki/Efficient-market_hypothesis
marcus_of_augustus
Legendary
*
Offline Offline

Activity: 3920
Merit: 2349


Eadem mutata resurgo


View Profile
May 22, 2013, 03:49:08 PM
Last edit: May 23, 2013, 03:45:48 AM by marcus_of_augustus
 #12

... his "weak form" definition of 'efficiency' seems suspect.

There are also robustness, dynamic response, incorruptibility and other properties for why free markets are desirable.

Casting an old chestnut from economics into a rigorous classic math problem framework like P=NP seems pretty contrived. Brain candy, but useful?, nup.

digitalindustry
Hero Member
*****
Offline Offline

Activity: 798
Merit: 1000


‘Try to be nice’


View Profile WWW
May 22, 2013, 03:54:27 PM
 #13

This paper will not be accessible to you if you aren't familiar with formal mathematics and computational complexity theory.

TL;DR: Either economists are wrong about their efficient market hypothesis, or computers have a shitload of computational ability that computer scientists just haven't been clever enough to exploit yet.

As long i can still gits my DrUgZez with them ther bzitk01nz, sall good dawg. Word

+1 gold : D

- Twitter @Kolin_Quark
digitalindustry
Hero Member
*****
Offline Offline

Activity: 798
Merit: 1000


‘Try to be nice’


View Profile WWW
May 22, 2013, 03:59:41 PM
 #14


Long-Term Capital Management:

https://en.wikipedia.org/wiki/Long-Term_Capital_Management

Just if you want to get some feedback about weather mathematicians make for good economists.



forest, and trees.

- Twitter @Kolin_Quark
hello_good_sir
Hero Member
*****
Offline Offline

Activity: 1008
Merit: 531



View Profile
May 23, 2013, 12:20:03 AM
 #15

Wow, I had no idea that people put so much faith in the efficient-market hypothesis.  I view it more as a rule of thumb, something along the lines of "the best estimate of tomorrow's price is today's price".

JamesTaylor
Newbie
*
Offline Offline

Activity: 30
Merit: 0


View Profile
May 23, 2013, 12:23:38 AM
 #16

It's widely accepted in the scientific community that P!=NP. Not sure, but most scientists "think" so.
caveden
Legendary
*
Offline Offline

Activity: 1106
Merit: 1004



View Profile
May 23, 2013, 07:52:57 AM
 #17

There are also robustness, dynamic response, incorruptibility and other properties for why free markets are desirable.

The Austrians give very solid arguments on why free markets are desirable (there's no school of economics which stands more for free markets than the Austrian school) and they reject the efficient markets hypothesis.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!