While this is a fun, the title is a little strong.
There are three limitations (whuch apply to many papers about P=NP).
1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error.
2. Markets could be efficient if P=NP and we know how to solve NP probkems in P, and we do it. The title makes it sound like the market will already be efficient if P=NP, which isnt true.
3. Even if P=NP, the polynomial could still be big enough the market cant be efficient. Similarly, P could not equal NP but the expoenential be small enough markets can still be efficient in reality.
On two, as this appears to be a cross disciplinary paper, it's important to consider that some economists currently claim markets are efficient (the efficient market hypothesis, which is like a big open question in economics). By drawing a link between the EMH and P=NP (which many computer scientists believe is unlikely) the author is linking two open questions with opposing beliefs. So I think point two is sort of a technicality that with context it should be understood that the author is specifically talking about two open questions as they stand today.
Also to further hammer home the point, due to the phrasing of the EMH, although no one may currently be using P=NP, markets would still have the efficiency property now even if no one is exploiting it. Perhaps this sort of vacuously true statement rubs you the wrong way (like it does me a bit) with the strength of the "if and only if" the author used. But if you read "markets are efficient" as the EMH then it is still a valid literal formulation.
On three, sure that's great for reality. But for the formulation of markets being efficient as an inherent property (again the EMH) of markets, the size of the market could be held as effectively infinite (or at least extremely large) and the property should still hold. At some point the size of the theoretical market will explode the polynomial, and for the EMH to hold P=NP must be true.
In economics, the difference between "efficient market" and "epsilon away from efficient" is very little.
IE, it is almost as good.
So sure, maybe the market isn't 100% efficient. Maybe it is instead 99.99999% efficient, and that's good enough.
Or in other words, The author of the paper is trying to be clever, and in the process he kinda misses the point of why the efficent market hypothesis is important to begin with.
* Economic systems are optimization algorithms on an NP hard problem. Hence markets have no special efficiency capabilities, they are simply a choice of optimization algorithm, there may be better ones out there with more favorable properties. Any optimization algorithm with similar resources could have effectively equivalent efficiency. This destroys the economic calculation problem.
* That you are wrong about the small epsilon. You can't make even that kind of guarantee in the face of NP hardness. What the market has a state may be wildly far away from the optimum, the market could be stuck in a local minima, and without P=NP you can't even know how far from optimum you are. Without a complexity class for markets you can't even begin to discuss it's properties, and that's what this paper is an attempt at.
It is your cleverness that misses the point, the author is trying to attach 21st century computational theory to economics (he may be wrong, but economic theories aren't going to help disprove it) and it's going to have some consequences.
The concept of NP-complete is different form the concept of np-hard to approximate in any way. The question if a particular problem is hard to approximate is typically a diverse and interesting research area, that does not have obvious answers.
For example, it has been proven that the well-known traveling salesperson problem on metric instances (i.e., instances satisfying the triangle inequality) can not be approximated within around 1.008 unless P=NP, and there is an approximation algorithm that has factor 1.5.
I have not read the above pre-print, but from a cursory glance it does not discuss theoretical approximation hardness at all. It does have a section on approximations, but it is hand-wavy and fluffy and uses a colloquial/non-strict meaning for approximation.
This is why I support the authors research, without knowing if it even is NP complete (as this paper claims) we are faced with it being NP hard. Without studying the problem, we can't even begin to find approximation algorithms.
The paper claims NP-completeness AFAICS, so I thought that was what you meant. Sorry if I misunderstood.
There are problems that have approximations that can get arbitrarily close to the optimum. One particularly interesting case IMHO are so-called polynomial approximation schemes. These schemes can be used to create an approximation algorithm for any choice of approximation factor and that algorithm will have a polynomial time complexity, but the polynomial will depend on the actual approximation factor chosen.
I agree that it is an interesting problem to study, especially since it meshes well with my own biases that the efficient market hypothesis is too strong.
Not in the face of generic NP hardness. From your own link, even NP completeness is not enough.
> Any strongly NP-hard [which may include strongly NP-complete] optimization problem with a polynomially bounded objective function cannot have an FPTAS unless P=NP
I was criticizing someone for claiming the author's work is pointless. The author's work is an attempt to find a complexity class for markets (and the problem they solve). If we know the complexity class then maybe there is a PTAS. But without the author's work you can't begin to claim there is an epsilon.
Markets don't need to be 99.9999% efficient either. Central planning can have a wide variance in efficiency. It could be substantially more efficient or extremely inefficient. If markets are able to reliably produce more efficiently year after year, even at the cost of lower peak-efficiency, then markets can still triumph in the long run.
I don’t think economists claim markets are efficient. There’s far too many examples to the contrary - see amazon, wellsfargo, and Verizon as examples. While those companies do technically have competition, they operate with significant market power.
Also, I once heard an Econ explain EH as “true if enough people operate under the assumption that it is not true”
Edit-After waking up a little more, I’m not entirely sure of my statement that amazon, wellsfargo, and Verizon serve as examples against EH. But the later quote I heard from someone with 30+ years of research.
The efficient market theory is that all information, public and private, is incorporated into all stock prices at all times, so there's no point to researching companies to try to outperform the stock market. I don't think anyone believes it is literally true, just that it is a good model for most stocks most of the time. If everyone believed it then no one would bother to research stocks, and the markets would be less efficient.
That's a far more limited claim. There's a very common claim that "markets are efficient". Extending to all markets all the time. Explaining why market based solutions are the best way to provide health care and education and other (arguably common) goods.
But many markets (the labor market, the health care market, etc) work in such a way that it's ridiculous to assume that most participants know all public and private information all or most of the time.
The EMH is specific to asset markets. So stocks and bonds basically. No (respectable, well-known) economist has ever argued that all markets are always efficient.
Also what people mean when they say markets are efficient in other contexts means something very different. The EMH specifically describes how quickly and what kinds of information get incorporated into asset prices. It doesn't make claims about how markets organize production or optimize utility without centralized direction, which is usually what people mean when they say free markets are efficient.
I think a lot of confusion has arisen from the very general-sounding name of the hypothesis which does not reflect its relatively narrow claims. Not that I buy the EMH (no pun intended), but that's a different story.
EMH that this paper refers to is about financial markets. In other areas of econ, no one is claiming that markets are efficient, in fact most of econ talks about "first best", "second best", "losses in efficiency", etc.
So called "Perfect Information", as you point out, is an important requirement of the efficient market hypothesis, but not the only one. It also requires fungible goods (e.g., if I start making bicycles that are better and cheaper than your bicycles, they will necessarily sell more. That's often not the case, especially if there is strong branding).
Another requirement is that entrepreneurs have fair market access to capital. This assumption is true in many developed countries, but not in many developing countries where you need connections to obtain a loan. But even in developed countries, it's difficult to get extremely large loans on the merits of the financials alone, which explains why large infrastructure projects like highways, airports, and power-plants often don't get built solely by the private sector.
Private information here refers to whatever insights you bring with your research. The point is that if you gain some private information (by being a quant, analyst, etc.) you would immediately trade on it and the price would then start reflecting your views.
Also EMH, and that's the point Fama uses a lot to battle critics, does not put a time frame on when the price adjustment happens.
In a truly efficient market, you wouldn't need to haggle about the price. You would have a slew of options that you could choose from, and would choose the option that best fits your demand. In an efficient market, if you were ever being overcharged by a company, another company would pop up overnight, and you would immediately switch from one to the other. No haggling required, just knowledge of what's available and easy movement from one option to another.
This. Economists and decision theorists like Herb Simon have been actively modeling "bounded rationality" since the 70s, but well before that, literal interpretations of efficient market theory were limited to those with something to sell (mainly to regulators). There are limits to human (and corpory) rationality that kick in way before P?=NP.
There is an impedance mismatch between the terminology in economics and CS. CS is at it's core a hard math discipline, and absolute statements are used a lot, and they differ quite a bit from what people outside of the field understand. This paper assumes a basic knowledge about CS theory and economic theory.
While you're right in your points here, the CS aspect of this paper leans on the CS theory. When a computer scientist say, "we cannot do this efficiently" it means, "We might be able to do this efficiently for some instances of the problem, but not for all instances". And when the scientist say "we can do this efficiently" it means "we know how to solve this in a way that when we double the input size, the difficulty will be a fixed factor larger. But it might be infeasible to solve any instance of the problem what so ever".
The result also exploits how the notion of efficient markets doesn’t include the computational time and cost of detecting the arbitrage opportunities, and so should be updated.
1. in reality, nothing ever is continuous, and those small errors are black swans.
2. PN!=P not because we can't solve it, but because it is impossible to solve, because there are more possible solutions than space we can use to model them. (oversimplified, i know)
3. que?
Most people seem to read this as a proof that markets are inherently flawed and as lending support to their ideological distrust of market economies. I think that if the authors thesis holds true and p indeed != np, this kind of conclusion could spell an even bigger problem for those who advocate to agument or replace market economies with another, typically more centralized, form of economic calculation. Allende's cybersyn famously used linear programming (P) in order to centrally 'simulate' and improve upon more regular market mechanics. If the authors thesis holds I think it's actually an argument in favor of the economic calculation problem talking point of Hayek and the like: efficient calculation of economic distribution problems is impossible and flawed dynamics of the market are probably close to the best approximation we can afford.
When I tried to read about Allende's cybersyn all I could find are a few retro-futuristic furniture, but no meat whatsoever about the kind of software that was behind. It looked like pure PR to me. Do you have good sources about it? It has always intrigued me.
Personally I think it is very unlikely that the markets are close to the best approximation we can afford. The current market-making agents use limited intelligence on limited data. It is an efficient system in the sense that it beats randomness and it beats a central (human) intelligence with (allegedly) superior access to information.
The project was very short-lived, but (IIRC) the primary designer was Stafford Beer (https://en.wikipedia.org/wiki/Stafford_Beer) who based the work on his so-called Viable System Model (https://en.wikipedia.org/wiki/Viable_system_model). For the fundamental theories of the time you'd want to read Beer's works as well as those of his contemporaries, who espoused competing theories and methodologies. (I say "at the time" but the state of the art never really changed. Project Cybersyn is a fascinating chapter in the long-history of AI, and if there's any dominate thread to AI it's one of diminishing expectations and migration to ever more circumscribed problem domains.)
As I mention in my Amazon review the author, Eden Medina, seems to have compiled a ridiculous amount of material but only a fraction of it bleeds through into her book. The book is fascinating but if you're interested in the theory and history more generally then the book's bibliography is priceless.
It's been awhile since I read the book but here's one lasting impression: one of the biggest problems with Project Cybersyn was communication between producers and consumers. Much of the budget and time was actually spent on telecommunications infrastructure and then figuring out how to get people to use it properly. Which hints at one of the most important functions of a market: price signaling. Regardless of whether a market is efficient, given the dynamic nature of a complex economy any system you setup that tries to centralize price signaling (capturing pricing information is a prerequisite for processing it and generating optimal allocations) seems like it'd very quickly become antiquated and a hindrance. Markets may be inefficient but at scale not only are they remarkably powerful distributed computation engines, they co-evolve with the economy. But that doesn't mean there isn't room for applying these techniques in sub-domains (e.g. trading engines, city governance, etc), improving overall efficiency.
I'm interested in this. So far, the best resources I found are:
- "Red Plenty" by Francis Spufford, a mix of fiction and non-fiction about planning experience in the USSR. It includes a rich bibliography and references to papers published over the past 70 years around this issue.
Check out "Towards a New Socialism", by the aforementioned Cockshott and Cotrell. Cockshott himself is a computer scientist and proposes planning the economy based on solving a linear system of labour inputs.
That reminds me of Scott Aaronson's post about the early signs a complexity paper is unlikely to be valid: https://www.scottaaronson.com/blog/?p=304 Not tex is the first point.
Frankly, everybody with a bit of economic common sense knows that efficient market hypothesis (EMH) is just a weird theoretical nonsense which is nowhere close to describing real world.
If you want a full critique, read Steve Keen's Debunking Economics, it has a chapter on EMH.
Oh and by the way, there is quite a bit of people who believe that P=NP. Most famously Donald Knuth. I recently became convinced about that as well.
Amusingly enough, the first thing that a rational person would do upon discovering a relatively efficient algorithm to solve NP problems would be to cash in all the Bitcoins. Thus proving in practice that no, markets are not really efficient. :-)
If you want to do the 'scientific arguments' thing, then surely it is up to the EMH proponents to convince the rest of us, while the rest of us stick to the null hypothesis.
I gave a citation. When I say "everybody with a bit of economic common sense", I mean everybody in economic profession who is able of some elementary reflection on what they are doing. Even most neoclassicals (which is probably the only school where somebody actually believes in EMH) know that many of the theoretical assumptions are bullshit. Another classic example, aside from EMH, is SMD theorem.
I am pretty sure that most economic Nobel prize winners do not believe in EMH, from the top of my head, Akerlof and Kahneman.
You gave a link to a popsci book whose Wikipedia Criticism section is ... unforgiving and relentless.
You then double down on your True Scotsman fallacy, mae a sweeping unsupported claim about a nebulous group of people, and follow it up with another conjecture about another group in an attempt to appeal to authority.
So do better! Find me an economist who truly believes in EMH and is either not a neoclassical (that's about half of all economists) or makes some real-world economic decisions (like in a central bank) or has expressed his belief in support of EMH after 2008 crash.
I gave you two Nobel prize recipients who actually wrote famous articles explicitly outlining market inefficiencies.
Regarding Steve Keen, I don't have my copy handy, but I am sure it has plenty of additional citations. While it is written in accessible style, it is certainly not unsupported. (I personally think that every student of economics should read him, but it's up to each individual what they want to do with their free time.) Many post-keynesians I have read expressed similar dismay about EMH.
> Debunking Economics exposes what many non-economists may have suspected and a minority of economists have long known: that economic theory is not only unpalatable, but also plain wrong.
Plainly alludes to the fact that the book is not mainstream economic theory. People arguing for minority views of complex subjects find — rightly — that the burden of proof is on them, and not the other way around.
Related: it’s not in the least bit surprising to see the book make an appeal to common sense over “those experts”. Truly we live in the age of Trump and Farage.
So I actually opened Keen's book - and it's more damning than I remembered. He quotes evidence that two major proponents of EMH - Sharpe and Fama - have made very critical comments as to its (EMH) empirical validity.
Isn't it also ironic that you criticize the book as being pop-sci by perusing Wikipedia? You know, in both cases, being pop-sci doesn't imply being wrong.
EMH is supported by the existence of Index Funds. So the truth of EMH depends on any point in time where the answer to the question of "Do Index Funds on average earn more than Private Funds?" is yes.
It's not even binary and is not a static property, just like our laws are just a proxy to a question of what is ethical or moral; and the truth of their purpose is entirely based on the historical context.
Not really. Index funds depend on the markets being efficient enough that the cost of finding the inefficiencies is higher than the gain from finding them. The more people who blindly invest in markets, the less efficient the market is in reality, and the more possible gain for those who do research.
Note that I said "people invest in markets", and not index funds above. There is a subtle differences, modern index funds are not true market indexes. There are fund managers who trade actively - however they trade mush less often than a traditional actively managed funds and with different rules. The managers do watch earnings reports and sell bad stocks, but the managers are also in for the long term and re willing to wait out a downturn. The managers also know they are judged by the index, and so bad stocks are not a negative in the same way that active funds are judged. Thus an index fund trades much less often, but they are not really a buy the index as published.
What I am saying is that the definition of an inefficiency in the market is the information that only a closed subset of the market has access to.
Let's take an example: China. While they keep the image of a purely capitalist environment, every company above a certain size is expected to have some sort of government control. That would be the inefficiency of that market, because at that point people stop making decisions based on what the company wants but rather what government wants. You can't have open access to the strategic planning by the government.
Besides, you're clearly trying to argue definitions rather than trying to take a step back and realising that I am arguing abstracts rather than specifics in the first place. In other words - what you're saying isn't denying what I said; it's just embodying the concepts in the real world.
For example: _any_ true real-life index fund would always need to trade at a certain point, and that has to be done by someone. So yes - an index fund is just a "glorified" version of a private fund; because people are still managing it at a certain point. But the reason it still makes money is because markets are efficient.
I am not sure I understand. If EMH was true, they should perform the same, no?
I would argue that belief in EMH is supported by existence of index funds. But index funds are also supported by laws that require certain level of openness and information sharing (such as laws against insider trading). When this information sharing is not enforced by law, it is a major source of market inefficiencies.
> "But given that there are 3n patterns to test, finding a solution, as opposed to verifying one, requires O(3^n), i.e. it is exponential in the size of n. For small n, this is computable, even though it is exponential. But as n grows, it becomes impossible to check every possible pattern quickly."
If a strategy is a sequence of BUY-HOLD-SELL decisions, then just because there's O(3^n) strategies doesn't mean you need to evaluate them all. It seems pretty easy (if a strategy is only defined in retrospect) to define a greedy algorithm that finds the optimal strategy. (see page 16.)
The author goes on to compare this to the Knapsack problem (pg 19). The thing that makes the Knapsack question (and NP-complete problems generally) hard is that greedy algorithms don't work (as far as we know), whereas it seems like a greedy algorithm work for the problem the author has laid out.
This paper is rubbish. Trading is ultimately a partial information, sequential game with an unknown number of participants whose payoff functions (and utilities) are also unknown. Could the market be closer to being efficient if P=NP? Likely. Does P=NP imply efficiency? Not at all.
On top of that, the argument rests on the kind of error you expect to see freshmen making in a discrete math course:
> The basic argument is as follows. For simplicity but without loss of generality, assume there are n past price changes, each of which is either UP (1) or DOWN (0). How many possible trading strategies are there? Suppose we allow a strategy to either be long, short, or neutral to the market. Then the list of all possible strategies includes the strategy which would have been always neutral, the ones that would have been always neutral but for the last day when it would have been either long or short, and so on. In other words, there are three possibilities for each of the n past price changes; there are 3n possible strategies.
There are 2^n possible histories of length n. If a strategy maps each history to one of three positions, there are 3^(2^n) strategies that consider n bits of history.
Is it even theoretically possible to show that markets are efficient on purely theoretical grounds? As a thought experiment, imagine that all human brains have a weird defect that causes them to always ignore some specific kind of information when making pricing decisions, including when they write software dealing with those decisions, and under all other conceivable circumstances. In that case, it seems to me, it would be impossible to decide on purely theoretical grounds that markets are efficient because it strictly depends on the empirical observation that human brains have this weird defect. I could imagine the other way around to work, i.e. that there could be an obstruction to markets being efficient that can be shown to exist on purely theoretical grounds. But no matter what the answer to the second question is, in no case could you arrive at an »if and only if« result without including the empirical observation that brains do not have this weird defect.
The entire premise of this paper is complete nonsense, and serves only to demonstrate the authors complete lack of understanding when it comes to the subject of markets.
"Trading is ultimately a partial information, sequential game with an unknown number of participants whose payoff functions (and utilities) are also unknown."
Markets in general are essentially an infinitely-armed bandit problem where everyone plays whether they know it or not, and resources are allocated over time in a manner not unlike evolution.
You seem to be missing the point. Markets were and possibly still are widely considered weak-form efficient. This is a disproof of that conjecture by showing an inherent contradiction between widely believed properties, ie. P!=NP and markets are weak-form efficient, therefore at least one of them is false.
Edit: "Does P=NP imply efficiency? Not at all." This isn't even a claim of the paper. The paper is claiming the opposite, that market efficiency is true only if P=NP.
Interesting topic and thought experiment. But this theory is not very fleshed out and not at all convincing (especially the part regarding using an existing efficient market to perform computation for anything other than price of the underlying instrument, i.e. what the computation is intended for). The following quote sums up how the author makes very open ended assumptions:
> So what should the market do? If it is truly efficient, and there exists some way to execute all of those separate OCO orders in such a way that an overall profit is guaranteed, including taking into account the larger transactions costs from executing more orders, then the market, by its assumed efficiency, ought to be able to find a way to do so. In other words, the market allows us to compute in polynomial time the solution to an arbitrary 3-SAT problem.
In reality, most financial markets are pretty efficient but none are perfectly efficient -- if they were perfectly efficient, it would imply not only perfectly efficient trading systems and an inability to get an 'edge' on the market, but also perfectly efficient market systems, which are limited by technology, conventions, and regulations (for example, significant inefficiencies arise in US securities from not being open all the time, with very little liquidity still available in the 'after hours' markets). To achieve even 'pretty good' efficiency requires significant energy, and I'm not sure I understand how the author can imply that the energy used in the past to calculate the current price is equivalent to the energy to verify the current price. As a trader, I can tell you that most market participants do not care to verify past calculations of the current price; they only care about the future price, and will generate an action from the differential between the predicted price and the current price.
> I'm not sure I understand the author's implication that the energy used in the past to calculate the current price is equivalent to the energy to verify the current price.
That's just what P = NP means: the cost to verify a solution is the same as the cost of finding one.
And asymptotically is not the right word either, because n^3 is asymptotically different from n^2. You probably meant poly-time reducible, whichs is quite different from "the same".
Agreed, I was also quite skeptical about the section you quoted. It seems like a much more hand-wavey proof than I'd expect to accompany an important result like this. Surprised that it was published (in a journal called Algorithmic Finance, which seems respectable enough) in this form.
I have always been puzzled by why we as computer scientists give such importance to P vs NP. I always thought that even if P = NP the solutions might still be much harder (but only polynomially) to find than to verify. I always get angry when people say that P = NP would mean that problems would be equally as easy to solve as to verify. So, because of that, P v NP always seemed irrelevant to me.
But in the article, there is an interesting section on that:
> If P = NP, even with a high exponent on the polynomial, that means that checking strategies from the past becomes only polynomially harder as time passes and data is aggregated. But so long as the combined computational power of financial market participants continues to grow exponentially, either through population growth or technological advances, then there will always come a time when all past strategies can be quickly backtested by the then-prevailing amount of computational power. In short, so long as P = NP, the markets will ultimately be efficient, regardless of how high the exponent on the polynomial is; the only question is when, and the answer depends on the available computational power.
So this section, if I understand it correctly, says that problems in P are easy because the computational power in the world grows exponentially and we can assume that they will at least once become feasible to solve.
That's an interesting way of looking at it. Is this really the reason why we consider polynomial problems much easier than NP-hard ones?
It is important to bear in mind that this paper does not attempt to quantify how much market inefficiency results from not having polynomial-time solutions to the problems in NP, or how much different things would be if we did [1].
The importance of the difference between P and NP appears to be much greater in domains that are starkly discrete, such as cryptography, than in those that are approximately continuous, like finance, where there are often approximate methods in P that are very effective and efficient, at least for most real-world cases.
[1] Only in the last section does the author look at all at real market data, and there only to look for evidence in support of a weak prediction from the thesis. This is so riddled with uncontrolled factors that it tells us nothing about the quantitative consequences of N != NP on market efficiency.
No. The reason why computation in P is considered tractable is because the exponents in polynomial coefficients in complexity analyses tend to be small. Linear-, quadratic-, and cubic-time algorithms dominate P, and we pride ourselves on finding ways to reduce those exponents. Some problems in P, like matrix multiplication and context-free parsing, have been analyzed to death this way.
We give importance to this question because it is open, it is big, it relates to many other parts of computer science, it has real-world implications, etc. The fact that you don't think this question is important likely means that you don't have the complexity-theoretic background required to appreciate the stark deepness of the question. This isn't bad, but it's myopic.
Well I'm trying to understand why this question is big.
The fact that the exponents tend to be small in the algorithms that our puny brains were able to produce does not convince me one bit that all problems in P have algorithms with small exponents.
Why are you so sure that P vs NP is important? Does it really relate to so many parts of computer science?
I do agree that complexity analysis is a very (perhaps the most) important part of CS. But that does not necessarily mean that P vs NP is a fundamental question.
RSA wouldn't break even if P = NP. Even if we came up with a polynomial algorithm for integer factorisation in could have a much higher exponent than the multiplication required to verify the result.
This is what bothers me the most, people saying that P = NP implies that solving a problem is as difficult as verifying a solution. That's simply not true: P = NP implies that solving a problem is as difficult as verifying a solution (modulo polynomial reductions).
The part about ignoring polynomial reductions seems very important to me. Otherwise I could also say that: "all even numbers are the same", when I actually mean: "all even numbers are the same (modulo 2)".
Would you care to convince me why we chose to ignore polynomial reductions and not some other complexity class?
The best explanation I see is the fact that different Turing machine formulations (single-tape, multi-tape, one-way infinite, two-way infinite, ...) and also the random access machines have polynomial reductions between them. But even this does not justify the importance we give to P vs NP in my eyes.
There is a reasonable-to-read paper [0] that explains everything; I will only share a few responses to your concerns.
"Our puny brains" have no problem constructing O(n^100) or similarly-ridiculous problems. Here is an informal survey [1] of several good examples. In my previous message, I indicated that matrix multiplication and CFG parsing are good examples; they are both cubic-time but we have come up with even cheaper algorithms for special cases, like sparse matrices or LR(k) grammars.
Whether P equals NP is not only a fundamental question, but it's the first of infinitely-many questions about the "polynomial hierarchy" or PH, a tower of ever-more-complex classes. And part of why the question is so important is that deciding whether P=NP is actually a problem in a higher rung of another complexity class further up in PH! P!=NP is like the first of an infinite family of very very difficult meta-proofs about complexity.
"RSA wouldn't break" because PRIMES is already known to be in P, via a famous paper titled "PRIMES is in P", and RSA keys are already sized to have impractical exponents.
What P=NP implies is much more powerful. First, let's consider the actual cost of a poly-time reduction. P is self-low, which means that P with a P oracle is equivalent to P. So if P=NP, then the cost of a poly-time reduction can be rolled in, and the entire problem is still in P.
Now, which problems would be transformable via P=NP? Well, we typically assume that the solution would include a poly-time reduction for 3SAT instances into some P-complete problem. Okay, great. However, we know that 3SAT can't be transformed opaquely; if this transformation exists, it must be able to examine and specialize the structure within each specific 3SAT instance. So we'd get one powerful theorem about logic (specifically, about SAT). But that wouldn't be the end.
We'd also get transformations for the following NP-complete problems, and each transformation would embody a free theorem about the nature of the structure of all instances of the problem ([2] for a bigger list):
That's some serious free theorems! There's no reason to expect that whatever would give us so much stuff for free would be easy to prove. In fact, it's quite the opposite: The fact that any NP-complete problem, if it yielded, would give us deep insight into all of the others, should give us extreme pause before hoping that P=NP.
As far as a I can tell the fact that PRIMES is in P doesn't mean breaking RSA is. The problem in rsa is integer factorization for which we do not know whether it is in P. (But also do not know for it to be NP-complete.)
But here you are actually supporting my point: event in that case we could choose sufficiently sized keys.
2)
And yes, the fact that P is self-low does seem to be the best justification we have to give such importance to P vs NP. That's also somewhat related to what I was saying about Turing machines and random access machines having polynomial reductions between them. But that's just because we decided to ignore polynomial reductions.
Continuing my example with even number being the same: We can see that multiplying an even number by any number yields an even number. Does that in any way justify ignoring the multiplication alltogether?
P with a P oracle really is equivalent to P, but O(n) with a O(n) oracle is not O(n), it's O(n^2).
3)
We have many NP-complete problems that have practical algorithms that perform fast on real-world inputs. I don't see how getting a free theorem about K-COLORING would practically mean faster compilers if the polynomial exponent was galactic.
Last reply; the sun's up and work starts soon. I'm leaving breadcrumbs.
On RSA: You're right, but this is only the tip of the iceberg. There's a concept, "Impagliazzo's five worlds," which explains in fine detail how the various P!=NP and P=NP scenarios impact cryptography. Basically, whether P equals NP could be an easier question than another open question, whether one-way functions even exist. There are cryptographic practical implications.
On multiplication: You are correct that DTIME(n) ≤ DTIME(n^2). However, P = DTIME(n) + DTIME(n^2) + DTIME(n^3) + …
If you would like to consider that only some small sections of P are tractable, then that's an understandable stance to take. There is, as I've mentioned before, an entire subfield of computer science dedicated to trying to move matrix multiplication from DTIME(n^3) to DTIME(n^2).
On approximation: Integer programming is simply harder than approximation. That's all. The fact that the approximations are tractable doesn't slake our thirst for the precise answers. Moreover, we don't know how BPP and NP relate yet, so it could be that there are ways to solve problems exactly in NP by randomized algorithms. We've found a few hints at this already, but derandomization is a hard process. (We don't even know if BPP=P, although P≤BPP and BPP is self-low. The holy grail of derandomization would be to derandomize BPP to P.)
Finally, I really encourage you to take a bit of time to read the Aaronson paper I previously linked, because it explains all this in much more detail. You are free to continue to think that the problem is not interesting, but I encourage you to at least get a sense of why it is hard.
I don't understand why you are responding to me in such a condescending tone, but thanks anyway for the discussion.
I'm well aware that P vs NP is a very hard question (I have studied quite some complexity theory, although I am a bit rusty), I'm saying that it does not seem as fundamental (or interesting) to computer science as people believe it to be.
Isn't finding the optimised solutions to market transactions something that is part of the market too?
So, not only do you have the resource problem highlighted in sibling posts but also a recursion problem:
Vis, when the problem becomes solvable the optimisation must add the market transactions for the sale of resources to solve the optimisation, so now one needs to optimise that larger problem ... which again involves transactions, which shift the original optimisation.
If you can predict the optimisational perturbations needed to solve the enlarged system, then you might be able to break the cycle .. but won't you need to transact the processing of the perturbation, the optimisations of which will shift the inner optimisation.
The solution itself would be marketable, perturbing the market and negating the optimisation?
My instinct may be wrong but it suggests the market can't be [perfectly] optimised (but in practise that probably doesn't matter).
Optimising markets might be the extent goal of capitalism, but it's not the extent goal of the rich (in general) who would rather remain rich than have perfect allocation of resources.
Before people get too carried away criticising markets, check this quote from the paper.
> The results of this paper should not
be interpreted as support for government intervention into the market; on the contrary, the
fact that market efficiency and computational efficiency are linked suggests that government
should no more intervene in the market or regulate market participants than it should
intervene in computations or regulate computer algorithms.
well, governments should do both. Computer algorithms can be a very subtle form of power. And of course we should have a degree of public control over them.
Sure, but if what the author is saying is true, then it implies that there is nothing special about markets, and a system involving an equal number of humans and computers following some other optimization algorithm could achieve similar results in efficiency.
And if a government sponsored and modified such an algorithm in an attempt to optimize for equality (second only to efficiency of usage), such a system could be an effective socialism. It is at least an interesting avenue to consider if mathematical and computational parallels could be constructed.
> then it implies that there is nothing special about markets
How so? It implies simply that markets are not efficient. It does not imply that state control would be more efficient and it does not imply that markets are not the most efficient way of determining the value of a resource.
What it definitely says however, is that a government committee could not, in any way, successfully determine the value of all goods and fix prices based on that determination.
> It implies simply that markets are not efficient.
No it implies that efficient market states are an NP complete problem. And that we are likely approximating the optimization of efficiency (of the allocation of resources) using markets. Different approximation algorithms have different properties. Might markets be the best in every possible way, sure, but it's very unlikely given what we know about approximation algorithms. It's like one of the best variants in one way, perhaps that's the best way, but we should figure that sort of thing out. And that's what this paper is laying the ground work for.
> What it definitely says however, is that a government committee could not, in any way, successfully determine the value of all goods and fix prices based on that determination.
In it's editorializing about markets. Which isn't incorrect. But the larger consequences of efficiency being an NP complete problem means that there are many possible algorithms we could use to solve them if they are given equivalent resources. If those equivalent resources are thousands (or millions) of government panels then we should be able to mathematically prove equivalency. That's my point.
There is a method of solving an NP complete problem with millions of companies participating in stock markets?
Your question is not related to my point. And you'd have to at least answer it for markets first before I would bother to try. My point is that it is an interesting area of research, we should answer both questions and their interrelationships.
1. I don't think anyone has any illusions that markets are in a mathematical sense optimal. They are a distributed process with no global knowledge - it would be strange if they somehow achieved global optimality.
The real question is how efficient are they.
2. If you're serious about
> if a government sponsored and modified such an algorithm in an attempt to optimize for equality (second only to efficiency of usage), such a system could be an effective socialism.
The big problems you have to overcome are probably the Economic Calculation Problem [0] and the Principal Agent Problem [1]. I have yet to see any reasonable solutions proposed.
On 1: That's exactly the point of this paper. That's what the EMH claims, and what this paper is linking to P=NP. If this paper is correct then markets are not violations of P=NP, and a lot of economists are wrong (or P=NP).
On 2: My answer to both problems (any problems) is Turing equivalence. If one algorithm of people and computers can solve the problem, then so can another one with the same resources. And given our knowledge of how different optimization algorithms can give results biased in different ways, it should be possible to find an algorithm that biases better towards equality than our current one.
But again that's a theoretical justification, which is why it's an interesting avenue of further research. I don't have any concrete answers because that would require research on the problem I haven't (and don't have the resources to) conduct(ed). And to make it quite clear, it's entirely possible the answer of this research could be markets are always the best (which would be disappointing, but possible), but it seems more likely that we would discover some new systems.
Edit: The economic calculation problem is the EMH rephrased (which this paper is making clear is a valid criticism only if P=NP). So that problem in specific is invalidated by this paper.
Edit 2: The principle agent problem is solved by the "equal number of people" component. And the fact that markets often involve selling other people's resources through their governments and other representatives anyway (see Saudi Arabia selling oil to enrich only their leaders on our open markets; while they use slaves), so it's not like markets are somehow a perfect solution to this problem as they currently stand.
Equal number of people doesn't not solve the principle agent problem.
The idea of the principle agent problem is that the best person who is able to understand their own wants and desires is the person themselves.
Markets are currently the way that puts the maximum amount of control into each individuals own hands.
IE, a person has X resources, and they can trade them how they like because they are best able to understand what makes them better off.
If your solution is to take power away from an individual, with regards to how they spend their own resources, IE, by controlling their "means of production", you are going to run into the principle agent problem.
Also, with regards to the paper talking about P=NP is missing the entire point.
Sure, markets aren't 100% efficent. They could instead be 99.9999% efficent. And that's good enough and side steps the whole P=NP problem.
> The idea of the principle agent problem is that the best person who is able to understand their own wants and desires is the person themselves.
I don't see how markets are supposed to solve that when we allow countries with slaves to participate on the markets. Or landlords to exercise economic rent over the land that other people maintain and live on. I guess my point here is I'm not sure markets as we have them today solve that problem very well anyway.
> Equal number of people doesn't not solve the principle agent problem.
But it does. If your claim is that every person is an economic agent representing themselves on markets (which isn't true for many people, but sure let's go with it), then any equivalent system would have to factor in the amount of work they provide to the algorithms that are markets and provide an equivalent (alternatives might include surveys, bizarre computer generated questions, kickstarter style projects but with government/basic income style funds). That's fine, it's still an interesting direction of research, which would be necessary to understand the computational structure of economies.
The alternative claim, is that markets some how create a system that is greater than the sum of computers and people it encompasses... this paper deals with that by placing it squarely in the realm of NP completeness.
Equal number of people doesn't solve the problem. It has to be the SAME people, working in exactly the same way to make decisions for themselves. IE, you just recreated a market.
An equivalent system would have to have the same people, in control of their own resources.
If you just replace the people who are currently making decisions about themselves, with DIFFERENT people, them the principle agent is no longer making decisions for themselves. A different person is making thise decisions for OTHER people, which is the principle agent problem.
Surveys and computer generated questions sounds an aweful lot like other people making decisions over other people's utility functions and resources. IE, they are not the principle agent.
You'd have to prove that surveys or whatever are better at deciding what a person wants than the person themself.
Even if you have more resources, it is still different resources. It is still different people making decisions for what other people want.
It's not that it distorts the market, but it's one reason why the assumption that markets some how solve the principle agent problem in the first place is wrong.
My personal argument is that I don't believe markets solve either the principle agent problem or the economic calculation problem, and so to require them of other systems is hypocritical. But even if markets somehow do, then Turing completeness would strongly imply that there are other economic systems that also have those properties. Otherwise magic (which this paper is evidence against).
The market cannot be efficient because a large portion of public information is not true.
Even if all the information was true, there is still the problem that humans have very poor reasoning abilities combined with herd mentality which almost always overrides the reasoning part.
To predict the market, you don't need to understand the market, you need to understand people's distorted view of the market.
I don't think anybody would claim that even the weak form of the EMH applies in all cases. Like the idea that objects of different weights fall at the same speed it's an approximation that can be very close to true in some cases but can be badly misleading in others. If you've ever listened to economists talk about prediction markets they always seem to bring up the idea that markets with low capitalization have low efficiency.
And even looking at the highly capitalized stock market I know at least one story of a major player that got its start noticing a violation of weak-form efficiency and becoming very rich by fixing the violation.
There's no reason to think that actual markets are now finally efficient and in fact there are some that are publicly know, but which only bring a small return and require decades of investment to fix so nobody is interested in trying.
Based on a quick skim, this is not a good paper. Computer scientists writing on economics is great, it's helpful to grow new ideas in the field. Unfortunately they sometimes use economic concepts imprecisely at detriment to their question, methodology, and results.
That's the case here. This paper posits a definition of efficiency, but does not explain why that definition is correct or how it relates to other efficiency measures.
A better proof of arbitrage opportunities in markets is Wah 2016, which identifies actual arbitrage opportunities in actual markets.
Separately, what does "Since P probably does not equal NP" mean as a probabilistic statement?
And what is the correct way to concisely and precisely write: "most people familiar with the P = NP problem believe with varying degrees of confidence that P is not equal to NP, but so far no proof exists."
> Separately, what does "Since P probably does not equal NP" mean as a probabilistic statement?
It actually does have a formal meaning! This is one of the most interesting results (in my opinion) on the P vs NP problem. Given a random oracle R, Pr(P^R != NP^R) = 1. So given a random universe, it is almost certainly true that your version of P != your version of NP. At least that's how my theory prof liked to explain it.
As I understand it, his argument is that there might be information available that needs time to interpret. And that the time the market took to interpret the available data is not sufficient to gain the maximum insight possible. So that somebody with more computing power then the market could beat the market.
I don't see that as an argument against the EMH. I think it is inherent in the EMH that the market has more computing power then any individual.
I would say that it is the core of the EMH. That more people make better predictions. Because they have more computing power.
I always found it strange that the EMH is often defined as the market price including all available data. As if the data can simply be added without interpretation.
So just to better understand the issue of P=NP, am I right in assuming that an NP problem is like trying to build a neural net for image recognition?
In the sense that it takes a huge amount of time and images to train the thing to become smart (in other words, to go through the entire network of neurons one by one and assign better weight values etc) but when it comes to actually verifying if our network is smart all it takes is to run an image straight through the network?
And the issue of trying to prove N=NP is essentially trying to prove that there isn't a magical way to train a neural network with just one image of training data?
No, I don't think building a neural net for image recognition qualifies.
NP problems are essentially problems where the following two properties hold:
1. No better algorithm is known than using brute force -- generating every possible result and checking if it's a valid result.
2. Checking that the given result is valid is doable in polynomial time or better. (This is less critical to understanding, but essentially your `isValidSolution(input, solution)` function needs to take `O(n)`, `O(n^2)`, `O(n^3)`, (etc.) time or better.)
Essentially, a NP problem is a problem where you have to brute force the solution, but it's easy to know when you've found the correct solution.
If P = NP that means that there are no problems where this is true -- it would mean that any problem where it's easy to know if you've found the solution also has an algorithm for finding it more efficiently than brute force.
Your neural network example doesn't apply because training a neural network doesn't require brute forcing the solution space of the neural network weights. That would be crazy. So it's a problem in P.
Re1: the problem here goes a bit deeper, classically the NP problem is a problem which requires a non-deterministic turing machine to solve. Ie a machine that can explore multiple outcomes at once, even the entire problem space to some extend.
A non-deterministic turing machine can interprete multiple instructions (write 5 to tape and go to state 2 OR write 3 to tape and go to state 19) and (depending on interpretation) use the instruction that gives the result fastest or explore all instruction branches at once.
Note that the "OR" in there is not a classical if-else, it means literally the machine can pick one. There is no memory value that tells it which is correct.
Basically, problems that are polynomial on a NDTM will likely be NP on a normal machine (with some exceptions depending on the problem).
Re2: As above, verifying is actually easy as you can then simply follow the execution branch the NDTM picked on a normal deterministic turing machine.
Atleast this above is what I learned in CS course 2nd semester.
I've read a little bit about turing machines and there is also a variation that includes what is called an "oracle" machine. Do you know anything about that?
An oracle machine is usually a turing machine that can tell you things about other turing machines.
An example would be the Halting-Oracle, which can tell you if a program will halt or not without running it. (Of course, this oracle doesn't actually work since your program can have the oracle's output as input and simply do the opposite)
A NP/P Oracle might be an oracle that can tell you if a more efficient algorithm for your problem exists.
Such oracles can be setup to prove certain assumptions (or disprove) based on simply logical statements (see halting problem oracle above).
Oracle machines are also not really turing machines, it's usually assumed they can do the oracling in a single operation and they're usually a black magic box (there is no need to explain how they work, they're an abstract concept).
From "TRAINING A 3-NODE NEURAL NETWORK IS NP-COMPLETE":
We consider a 2-layer, 3-node, n-input neural network whose nodes compute linear threshold functions of their inputs. We show that it is NP-complete to decide whether there exist weights and thresholds for the three nodes of this network so that it will produce output consistent with a given set of training examples.
but trying to devise a program that can predict somebody's password without using brute force is a NP problem? Since its hard to discover what the password is, but trivial to check if it lets you in the vault?
I get the reasoning why people aren't sure if P = NP.
Here is another question.
What defines time? And what about a solution?
Consider the fact that in the theory of general relativity we have the twin paradox.
What if I sent a computer on a rocket at close to the speed of light and then on earth I had the same machine running the calculation that takes a million years, and then when the other computer gets back from it's interstellar vacation, I just have the computer ask the other what it's part of the solution is.
According to the computer that flew away the amount of time that it takes to solve the problem can be considered ~P in a way.
My intuition is telling me that this is probably the wrong way to think about time complexity though.
Time and solution are usually abstract concepts here.
The time a turing machine takes to solve the problem can be considered local and in absense of general relativity, it doesn't matter much.
When you talk about time in NP/P, you usually talk about the O Notation (Big O and friends) which gives you the driving factor of the time needed to solve.
Ie, O(n) = 2 + 3x + 9x^2 + 9^x is n^x complexity because this part of the equation will grow much quicker than the others. In reality of course, it can take a while for the biggest part to overtake which is why searching an array linearly in CPU cache can be faster than a hashmap.
The solution in NP/P is usually reduced to either a predicate being proven true or the answer being boolean or can be reduced to either. (ie, solving a jig-saw puzzle can be reduced to "is this jig-saw puzzle solvable" which can be proven by presenting a solution)
The problem you present is not in the scope of NP/P. You're already involving multiple computers and generally here, people still assume general relativity doesn't exist. Plus NP still holds because one computer simply accessed a blackbox function (oracle) while the other solved it in NP.
Time-complexity isn't the only complexity either, you also have space-complexity.
SC tells you how much memory you need to solve a problem. Or rather, how quickly that memory need will grow. You can trade a lot of NP problems to P problems if you have "NP" space complexity.
SC complexity won't spit out a byte-accurate estimation of memory but it can tell you that O(n) = 100 + 100*x will grow linearly in size (O = x) and O(n) = 100 + x^2 will grow exponentially in memory usage (O = x^2).
> According to the computer that flew away the amount of time that it takes to solve the problem can be considered ~P in a way.
No, since it can only save a constant factor of time. (Also, dragging random physics into a mathematical model based on a different view of the world isn't really helpful to understanding it. "Time" is computational steps, not seconds)
> And the issue of trying to prove N=NP is essentially trying to prove that there isn't a magical way to train a neural network with just one image of training data
No it's not. You can't do reasoning on bullshit inaccurate analogies.
I'm trying to summarize what I
remember on the topic, so if anyone finds something wrong, I'd appreciate a correcting comment :)
Without knowing too much about neural networks myself:
Theory stuff:
P, NP, NP-hard and NP-complete only refer to classes of complexity (of algorithms), i.e. you can "categorize" decision problems this way (by currently known solutions or mathematical proofs of lower and upper boundaries for complexity).
P contains any problem for which there is an algorithm that can decide it on a deterministic turing machine (read: abstract definition for a computer) in an amount of time that is growing polynomially with the size (n) of its input.
Example: Checking if a list contains a specific item can be achieved in O(n) time - just iterate through the list. Searching in a pre-sorted list (binary search) can be achieved in O(log(n)) time. This means that if your list is longer by a large factor, both algorithms will take accordingly more time, which means that the amount of computation necessary for the sorted case will grow much less than the generic case. Both problems are within P, though.
NP contains all problems that can be solved by a nondeterministic turing machine in polynomial time. If you think of your problem as an automaton with states, this machine could deal with ambiguous state transitions in an efficient manner, "magically" only picking those options that succeed. This is basically the promise of a quantum computer. P is thus a subset of NP, since the nondeterministic touring machine can do anything a deterministic one could do too.
You can still solve those problems on a normal computer, but not in polynomial time (unless P=NP, which is neither officially proven nor disproven until now).
Then there is the idea that you can solve problems using solutions for other problems merely by transforming the input in polynomial time.
NP hard problems are those which you could use to solve any other problem within NP this way. Those don't necessarily have to be in NP - their complexity could be even worse. There is an intersection with NP, though: Problems within NP that you can use to solve all other problems in NP. Those are called NP complete.
If you would now find a way to transform the input for an NP complete problem into one for any P problem in the same way (remember: in polynomial time for a DTM), then you would have effectively proven that P=NP.
On the NN comment:
I've always understood AI in general and especially trained algorithms to be heuristics. If you talk about P and NP, you're talking about mathematically proven solutions, so the comparison doesn't work out in the strict sense. On the same note, NNs are often used to solve problems that don't have strictly "correct" solutions. If your problem is "does image X depict a goat?", you won't get far with traditional means. A NN, on the other hand, trades accuracy (false positives and false negatives will happen) and up-front work (training with a dataset not provided by the actual problem instance) for speed.
It is related to the discussion though, since a generic trainig algorithm for neural networks actually will have a non-polynomial complexity as far as I understand (at least Google tells me so ;-) ). Note however that training a NN is also not a decision problem: The result is not true or false, but the resulting network.
Edit: Replaced a reference to sorting with searching for an item, since sorting is not a decision problem.
What I am trying to understand is why this is considered a solvable problem, when essentially you need to devise a method to find a better solution to the problem in order to prove that there isn't a solution.
Aren't all proofs flawed in this way?
Like for example, 2 = fish. Prove that there isn't an undiscovered mathematical axiom that makes this not nonsense?
Reading this comment thread is hilarious to a degree. I think that it really highlights how much noise gets thrown into a discussion when your naming becomes too relatable. Essentially bike shedding of theory discussion. If the Efficient Market Hypothesis has been called the “Fundamental Market Property Hypothesis M = H” or similar I doubt most would have made the comments they made. But because “efficient market” sounds to relatable most feel that they can comment without even knowing what the specifics of the EMH are.
Meh. Whatever your opinions on P = NP, the efficient markets hypothesis is unfalsifiable. You can only falsify a joint hypothesis of efficiency plus some model of information flow into a market.
Wait a minute, if the paper correctly links a theoretical definition of efficiency to the complexity class and indeed shows that markets can be efficient only iff. P=NP, then any future proof that P!=NP falsifies the thesis that markets are efficient. And most experts agree that if we ever get a proof, then it will be a proof of NP!=P.
Knuth is a notable exception, although he has to my knowledge never really vigorously advocated P=NP but merely suggested the possibility that P=NP and that the algorithms to transform NP problems into P problems could be very, very complex but still in P. Seems unlikely, though.
The author’s claim only applies to weak form of market efficiency.
The original Fama paper distinguishes between three forms of the EMH: weak, semi strong and strong.
The weak form only alleges that historical price info is fully incorporated in the current price. You can still make money by working hard and figuring things out from outside the price history.
The weak form applies to purely technical trading that extracts value from price history like momentum and the simple moving averages cross over studies you see.
Interesting. It is well known in the high-frequency literature that at frequencies higher than 5-minute one obtains market microstructure noise. The observations you observe do not fully reflect the "true" price. I.e. you observe bid/ask quotes with a spread and the "true" price is somewhere in between. This is due to the bid-ask bounce and other latency factors. How can markets ever be efficient if we can not observe the true price of something?
If you buy a call option, the market-maker buys stock to hedge it. That moves the underlier, and raises the price of the call option he just sold. The reverse is true if you sell a call (or buy a put).
Not only that, but there is a cost for all the people and computers that your order touches as it gets executed.
Without price impact from transactions, markets can't be efficient, because new information has to get priced into the market somehow.
I'm not familiar with high-frequency literature, but you can rarely measure something with 100% accuracy. Despite this, your house got built even if its measurements were taken with a +-0.5cm error. So if the noise is sufficiently small, you can know the true price with enough precision. I don't know if that is the case though.
From the paper: "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.
However, there has been no proof that there does not exist some algorithm that can determine satisfiability in polynomial time. If such an algorithm were found, then we would have that P = NP. If a proof is discovered that no such algorithm exists, then we would have that P ≠ NP.
Just as most people in the field of finance believe markets are at least weak-form efficient,
most computer scientists believe P ≠ NP. Gasarch (2002) reports that of 100 respondents to his
poll of various theorists who are “people whose opinions can be taken seriously,” the majority
thought the ultimate resolution to the question would be that P ≠ NP; only 9 percent thought
the ultimate resolution would be that P = NP.
The majority of financial academics believe in weak form efficiency and the majority of
computer scientists believe that P ≠ NP. The result of this paper is that they cannot both be
right: either P = NP and the markets are weakly efficient, or P ≠ NP and the markets are not
weakly efficient. "
What kind of markets get created when the input to the NP problem is 2^10000, I think our idea of markets are based on small scale transactions and extrapolations can't take into account intelligent agents. Also Arrow's theorem hints how small formals systems can't achieve agents desires. Anyway, I have only read the title not the arxig paper.
Somehow this seems to be a confusion of categories: markets are real-world mechanisms, while P and NP are mathematical abstractions. Does not compute. To the extent that it does, it's typical mathematical macroeconomic BS.
>markets are real-world mechanisms, while P and NP are mathematical abstractions
We use mathematical abstractions to model real-world mechanism every day for millennia.
Not only that, but there are all kinds of mathematically defined limits that no real-world mechanism can bypass, from a purely logical perspective.
If you only have 10 dollars and I give you 20 dollars, you'll have 30 dollars, not 500 -- that's a mathematical truth that absolutely holds in the real world too.
Well, that's a quite insubstantial point, to say the least. Mathematical theorems place upper and lower bounds on what is possible in the real world within almost every domain. Of course, there may often be other reasons why something is impossible, too.
They don't need to exist in mathematics either, but the outcome would be the same. You can't do the real-world analogue of squaring the real-world analogue of a circle.
Even if P ist not equal NP, hardness of efficient markets could be in APX2 i.e. computing a solution that is at most twice as bad as the optimal solution is in P.
First of all this paper leaves a lot to be desired in terms of rigor and it is for good reason not how mathematics is written by most mathematicians. It is very conversational and assumptions and derivations are jumbled together, while you sometimes find these in breakthrough papers from visionary mathematicians it often makes it harder to verify.
My understanding of the central argument in the paper is the following:
Definition: Let N be a positive integer denoting the length of the history, M be a positive integer denoting the number of assets. A market realization is an element of {-1, 1}^(NxM), i.e. M vectors of length n where all entries are either +1 or -1.
Definition: We call a function f: {-1, 1}^(TxM) -> {0, 1}^M satisfying f \circ s = s \circ f for s any element in the symmetric group S_M a technical strategy of lookback T.
The symmetric group condition just states that permuting the vectors of length T among the M assets is the same as permuting the output the strategy. I.e. that the strategy has no inherent preferences among the assets.
The payoff of a technical strategy s on a market realization h is given by payoff(s, h) = \sum_{i=T}^N s(h_{i-T, ..., i-1}) \cdot h_i where the indexation is in the time dimension i.e. h_i denotes a length M vector.
The budget of a technical strategy is budget(s) = max_{v \in {-1, 1}^TxM} s(v) \cdot (1, ..., 1). That is the maximal number of assets it wants to hold in any given state of the world.
Given a market realization h, positive integers B and K we say that h is (B, K) EMH-inconsistent if there exists a technical strategy s such that budget(s) <= B and payoff(s, h) >= K. If a market realization h is not (B, K) EMH-inconsistent we call it (B, K) EMH-consistent.
Claim (presented as a theorem in the paper): The problem of determining whether a market realization is (B, K) EMH-consistent is in P if and only if the knapsack problem is in P.
Claim: The weak efficient market hypothesis is true if and only if EMH-consistency is in P.
In the second part of the paper he indicates a model of an order book where he wants to encode 3-SAT as combinations of market orders. I do not understand how this is intended to work, i.e. if all information is available and incorporated into the market and the information generating process is stopped, and I have bid-offer spreads because of transaction costs, and I irrationally (remember I am not interested in the buying or selling the security, I am just interested in solving a 3-SAT problem, thus my actions should not influence the price generation process of an efficient market) enter an OCO-3 order to buy A, B or C at mid. Why should this result in a transaction? In the case (a or a or a) and (!a or !a or !a) I make one trade with myself in the case (a or a or a) and (b or b or b) and (!a or b or b) I make one trade with myself, but one of the problems is satisfiable the other is not. Now it seems obvious that by inventing new order types we can get order book rules that allow for complex computation to resolve clearing, however this is a problem with the proposed order types not the efficient market hypothesis? A (to me) equivalent avenue of investigation would be to imagine different order types such that to decide the clearing of an order book it would involve solving an undecidable problem - i.e. what are the most reasonable order types and order book rules such that we can encode the halting problem?
Not really. It means that the market incorporates all past data.
This paper is entertaining but it depends on the assumption that computing power grows exponentially forever and will eventually be able to solve all P problems at negligible cost. That assumption is clearly not justified.
And the belief that any market perfectly incorporates data, not a single point off in any stock, is basically a strawman anyway.
I don't know! I'm wondering! Because weak-form efficient means something different than strong efficiency, which is what you say when the market perfectly incorporates all data. Just out of curiosity, if the data doesn't go into the market, where does it go? Strong econ minds believe that prices do incorporate all the data necessary for valuation
Digital is a framework built on top of analog. Boolean logic is the foundation of all of our modern computing, and so we built all of our circuits around the ability to handle HIGH and LOW signals. What your describing seems to me like you're saying that leveraging an analog signal is the benefit of quantum computation. If so, I don't really agree. If not, then I misunderstood.
Either way, I suspect that the superposition between the change in value and the change in time, in relation to all of the other superpositions in value/time changes, is the true computational power of quantum technology.
(didn't set the date so in the document it's wrong, this was published 2010.)
It doesn't depend on P = NP, it's simply a rigorous proof that EMH is false.
Let's switch gears a second. Here's a famous elementary proof[1] that there are infinite primes. Suppose there are just finite primes, up to some largest. Multiply them together and add one. No prime divides the new number (because "every" prime leaves a remainder 1), so you've just produced a new prime. This new prime is larger than the largest prime in your finite set because you multiplied that by the rest of them and added one to get it. So this is a contradiction, you couldn't have had finite primes up to some largest.
Anyway if you think there might be a largest prime after what you just read, it just means you don't understand the proof. If you believe EMH might be true it just means you don't understand the proof that it is false.
Of course, nobody ever even hypothesized that academia was efficient :)
Maybe I'm being super pedantic and possibly confrontational (I apologise in advance) but it jumped out on me here. I think you've misunderstood the 'famous elementary proof' that there are infinite primes. You do not create a new prime as you have suggested (quoted below).
"Multiply them together and add one. No prime divides the new number (because "every" prime leaves a remainder 1), so you've just produced a new prime. This new prime is larger than the largest prime in your finite set because you multiplied that by the rest of them and added one to get it."
Instead you have created a number that may or may not be prime but definitely requires a new prime number (not in your set) to factorise it. Counter example: Take your set of prime numbers to be {2,3,5,7,11,13} then
(2.3.5.7.11.13)+1 = 30031
30031 factorises into 59.509 so you have found two prime numbers that are not in your original set.
EDIT: Responding to the edit above. The problem is that you claim that you make a new prime number by multiplying them all together and adding one. You didn't multiply all the numbers and added one to get the prime number, you multiplied all the numbers and added one to get a number (POSSIBLY NOT PRIME) whose FACTORS are prime numbers not in your original 'supposed' finite set. Your proof essentially lacks the step: IF new_number is prime: proof finished ELSE: factor new_number and show that at least one of the factors is not in your finite set.
EDIT 2: Counterexample number 2. Suppose your finite set of primes is {2,7}
(2.7)+1 = 15
So you have found 3 and 5 as primes that are not in your original set and are SMALLER than the largest prime in your original set. This is now a second mistake in your proof. Whether you are trolling or just too arrogant to see the mistake/error I do not know.
You're entirely correct. A very ironic mistake/misunderstanding for the parent post to make.
Edit: I've thought about this a bit more, and you can save the parent post by prepending a result like "Every number larger than one is either prime, or divisible by a prime smaller than itself". In this case you can then assert that your constructed number is prime. However, this result requires its own proof and was not mentioned by the parent post.
Technically, the parent post literally said "No prime divides the new number ... so you've just produced a new prime". It does not make the direct claim that the new prime is equal to the new number.
It is possible that the OP did not make the mistake that you are attributing to them, although best case is that the exposition was simply unclear.
Thanks, very charitable reading but doesn't work because next sentence I said that the new prime is larger than largest. As other poster points out if 2,7 are all your primes you produce 15, whose primes are not larger than 7 so the "new prime" wasn't referring to one of them.
But that's not how I argued. Instead I showed that 15 is the new prime because it's relatively prime to all the primes. (By the assumption we had started from all the primes.) And this is what falsifies the assumption.
I think my argument is fine and I don't need to address whether 15 is really a prime.
Your post says "No prime divides the new number, so you've just produced a new prime." What, exactly, do you mean by "produced"? You say produced, not "established the existence of", so it makes it sound like you are assuming a constructive argument.
Do you mean that the number you've produced is prime? Or do you mean that "the number you have computed is either prime or has a prime factors not in your list of primes, therefore, by computing the factorization of that number, you produce a new prime"?
The former statement is demonstrably false, the latter statement is true. Others have read your proof as stating the former, and I argue that the latter is a generous but not unreasonable interpretation of your phrasing.
Andrew, I perfectly see what you're saying, but I am telling you it is absolutely no problem that there's a false statement.
Remember that we are arguing from the false assumption that you start with the finite set of all primes, up to some largest prime, L. Call this false assumption A. It's fine to make false statements that follow from A, no problem at all. Indeed this is the point.
One definition of a prime is that there are no primes smaller than it in its prime factorization. We'll call this definition NSPIPF - no smaller prime in prime factorization. Is NSPIPF an OK test for primality? Sure.
So when you get to new_number, produce the prime factorization. Does it meet the definition of NSPIPF? Yes, because we made it relatively prime to every prime (under assumption A).
It passes primality test NSPIPF. Under A. And therefore is prime. Under A. (This is the part you and others object to, but it's absolutely flawless application of the NSPIPF primality test.) It doesn't matter that in some other way I could also get to a contradiction. For now this is what we do.
Under A, using NSPIPF primality test, we just proved new_number is prime.
Next we show that this new_number definitely wasn't in the set of all primes, since it's larger than L, having had L and a bunch of other positive integers as factors and then one added to that for good measure. It is at this point that we show explicitly that A cannot be true, because we used A to produce a prime that wasn't in the set of all primes.
It doesn't matter if that was a false statement!
I think all this is in my original comment and it is a flawless proof by contradiction. I asked you to "Suppose there are just finite primes, up to some largest" and you gave up when you started seeing false statements, rather than at the end of the paragraph where I presented the conclusion in black and white.
Nobody is contesting that the conclusion is true, just that the proof is unsound as written.
Here you've introduced a definition of prime that is different than the usual one, and is in fact self-recursive. NSPIPF is "no smaller prime in prime factorization". What is the first "prime" in this definition? Is it a number such that there is "no smaller prime in prime factorization"? What is the second "prime" in that definition? Is that the usual "prime factorization", or is it an NSPIPF factorization? In other words, how would you prove that 2 is prime given the NSPIPF definition?
It is more natural to talk about primality as a test that can be done independent of any assumptions about other primes, but rather as a matter of whether it can be expressed as the multiple of some number other than 1 and itself. That way we can make a precise statement about the product of the finite set of primes plus one without reference to the set of primes.
>It is more natural to talk about primality as a test that can be done independent of any assumptions about other primes, but rather as a matter of whether it can be expressed as the multiple of some number other than 1 and itself
This is clearly not what I was doing. I clearly referred to having no smaller prime factors. Anyway this aside is tiresome, it's like poking me for saying "every positive integer has a prime factorization" and then asking, okay, so what about 1 or something. I think my proof is fine and I'm not going to defend it anymore.
Suppose 2 and 7 are the only primes < 15. Then 15 is prime because its prime factorization couldn't contain any other number (2 * 7+1 makes it relatively prime to both 2 and 7 which under the supposition are the only primes < 15.) This is true if we suppose 2 and 7 are the only primes < 15, and that's just what the word "suppose" asks you to entertain.
This little mental exercise proves that 2 and 7 can't be the only primes in existence. It doesn't really matter what 15 really is or isn't. No need to add noise about it. We only care about the supposition, which you cut out of your quote.
Hope this explains why I didn't deal with the true status of new_number! It just doesn't matter.
However, I'm disappointed in you, in the other respondent, and in the moderation here, and I'm glad I made this alternate account.
I haven't heard of EMH before today and can't really comment on that.
But it seems to me that even in the example from your note the stock price will tend to reflect the the correct price. As you realease new information the factorization becomes more feasible and once it's feasible enough the stock price will get the correct value. Maybe we should amend EMH to say that asset prices fully reflect all the facts that are feasible to compute from the available information.
Anyway, the reason I'm writing this comment is to say that you should no be so sure of your proofs, especially because your proof of the infinitude of primes is wrong. This proof does not show that the new number (the product of primes + 1) is prime. It shows that none of the primes are factors in this new number and from that it follows that there must be more primes, but it does not follow that the new number is necessarily prime (it might be a product of another unknown primer and the others).
Sure, but you can't "amend EMH" to fully reflect all the facts that are "feasible to compute" any more than you can amend it to say that that asset prices fully reflect the "best feasible analysis". That's not EMH.
For the prime proof, the new number is prime as long as as it has no prime factors < itself, which we assumed at the start. This guarantees it's prime under our assumption and this falsifies the assumption. Doesn't matter if it's really prime.
Your proof for the EMH hinges on a very specific technicality -- whether the secret prime, P, is public knowledge, or to what degree it is public knowledge.
I think if we were to approach the EMH from a constructive or computability approach, we'd have to make that definition much crisper. That is, the feasibility of computing the factorization based on limited information determines whether the information is actually "available" in the sense of the EMH.
In the real world we can see things like drug trials that will determine the success of a pharmaceutical company. The information that the drug works or doesn't work, or has side effects, would be "apparent" to a hypothetical "ideal" expert in human biochemistry -- so simply knowing the chemical formula for a new drug, the information about its working is "available" in that sense.
If you can show an inefficient market experimentally whenever you want, that's good enough to disprove EMH. The EMH doesn't say, "All information is normally factored into the price, except for technicalities."
I like your drug trial example but a "hypothetical ideal expert" isn't assured to exist. Do you have an existence proof?
On the other hand, unique prime factorization is assured, we know that given infinite time anyone can factor any large number.
The EMH is usually restricted to "available information". This hinges on what "available" means.
I would argue that until the search space was reduced to the point where it would be feasible to factor the secret before another digit is revealed, the information is not "available" in any useful sense. So maybe, in some sense, this helps us narrow down a definition of what "available" means, but since real-world price signals are rarely something that is deterministically computable, I'm not sure that this would help to clarify the EMH.
In my drug trial example, such an expert does not exist, but if we're dealing with mundane real-world stuff, then the assurances that the proposed $1B gift to a random company would actually go through would have to be factored into any strategy -- why would I bother committing computing resources to factoring the number when in all likelihood the billion dollars would not handed over because why would anyone actually do that?
100 possibilities are really easy to test, though, so P must be fully available near the end. We can all agree it's not available at the beginning (subject to the methodology.) So it becomes more and more available over time, but that is not what the EMH says -- at all. If you are saying market prices will reflect information as a function of how "readily" available it is (for example how smart you have to be to see it), that is just not EMH.
For the drug trial example, again, I like it but perhaps such an expert is theoretically excluded? Your statement might be like saying "suppose there's a hypothetical O(n) halting algorithm that answers the halting problem in constant time for the length of the program it's testing." That's nice but there's a proof that what you've just hypothesized is impossible[1].
I am not exactly saying that an ideal expert in human biochemistry who can predict the results of drug trials is impossible, but how do we know it's possible? I mean, is chemistry guaranteed to be fully computable or something?
For your last point, I think that what I asked to assume (that the $1B transfer is credible, that the computer is secure) are nowhere near the size of assumption of something like "assume there exists someone who can predict biochemical reactions in humans without testing." Basically the legal instruments and secure computers I included are easy, solved problems that I ask the reader to assume are being implemented following best practices.
Individual comments effectively get silenced (or at least buried) by downvoting, changing the account you post with won't change that. You can get an account shadowbanned however which does reduce the visibility of all its comments but that's a different issue, I don't think you can trigger a shadowban automatically by downvotes alone (or maybe only in extreme cases).
And what I'm saying is that you literally can't when you get enough negative karma. I have three HN accounts and two of them have negative karma and can't post without mod approval.
Or it just says: You're posting too fast. Please slow down. Thanks.
There are three limitations (whuch apply to many papers about P=NP).
1. The market could still be efficient, because the situations which must arise to cause P vs NP problems are very complicated. In particular thry require very expensive indivisible things to buy, whereas in most situations we can treat things like shares as continuous with only a small error.
2. Markets could be efficient if P=NP and we know how to solve NP probkems in P, and we do it. The title makes it sound like the market will already be efficient if P=NP, which isnt true.
3. Even if P=NP, the polynomial could still be big enough the market cant be efficient. Similarly, P could not equal NP but the expoenential be small enough markets can still be efficient in reality.