We are interested in computation of arbitrage condition in financial market with friction. We consider a deterministic model with a finite number of financial assets and a finite number of possible states of nature. The future return of of each asset under each possible state of nature is given in the model. We derive a negative result on computational complexity of arbitrage in the case when assets are traded in integer numbers of shares and with a maximum amount of shares that can be bought for a fixed price.

本文研究摩擦市场中的最优消费-投资组合选择问题。当金融资产和自然状态个数为有限个以及摩擦局限于成比例的交易费时，可用原始市场或适当转换了的市场的无套利性来刻画最优消费一投资组合策略的存在性或充要条件。

In this paper we study the computational problem of arbitrage in a frictional market with a finite number of bonds and finite and discrete times to maturity. Types of frictions under consideration include fixed and proportional transaction costs, bid-ask spreads, taxes, and upper bounds on the number of units for transaction. We obtain some negative result on computational diculty in general for arbitrage under those frictions: It is NP-complete to identify whether there exists a cash-and-carry arbitrage transaction and it is NP-hard to find an optimal cash-and-carry arbitrage transaction.