This article is from the Anarchy FAQ, by Bryan Caplan with numerous contributions by others.
Probably the earliest minarchist attack on anarcho- capitalism may be found in Ayn Rand's essay "The Nature of Government." ("Minarchism" designates the advocacy of a "minimal" or nightwatchman state, supplying only police, courts, a legal system, and national defense.) Her critique contained four essential arguments. The first essentially repeated Hobbes' view that society without government would collapse into violent chaos. The second was that anarcho-capitalist police firms would turn to war as soon as a dispute broke out between individuals employing different protection agencies: "[S]uppose Mr. Smith, a customer of Government A, suspects that his next-door neighbor, Mr. Jones, a customer of Government B, has robbed him; a squad of Police A proceeds to Mr. Jones' house and is met at the door by a squad of Police B, who declare that they do not recognize the authority of Government A. What happens then? You take it from there." Her third argument was that anarcho-capitalism was an expression of an irrational subjectivist epistemology which would allow each person to decide for himself or herself whether the use of physical force was justified. Finally, her fourth argument was that anarcho-capitalism would lack an objective legal code (meaning, presumably, both publicly known and morally valid).
Rand's arguments were answered at length in Roy Childs' "Objectivism and the State: An Open Letter to Ayn Rand," which tried to convince her that only the anarcho-capitalist position was consistent with her view that the initiation of force was immoral. In brief, Childs argued that like other free-market institutions, private police would have economic incentives to perform their tasks peacefully and efficiently: police would negotiate arbitration agreements in advance precisely to avoid the kind of stand-off that Rand feared, and an objective legal code could be developed by free-market judges. Childs strongly contested Rand's claim that anarcho-capitalism had any relation to irrationalism; an individual could be rational or irrational in his judgment to use defensive violence, just as a government could be rational or irrational in its judgment to do so. As Childs queried, "By what epistemological criterion is an individual's action classified as 'arbitrary,' while that of a group of individuals is somehow 'objective'?"
Robert Nozick launched the other famous attempt to refute the anarcho-capitalist on libertarian grounds. Basically, Nozick argued that the supply of police and legal services was a geographic natural monopoly, and that therefore a state would emerge by the "invisible hand" processes of the market itself. The details of his argument are rather complex: Nozick postulated a right, strongly contested by other libertarians, to prohibit activities which were exceptionally risky to others; he then added that the persons whose actions were so prohibited were entitled to compensation. Using these two principles, Nozick claimed that the dominant protection agency in a region could justifiably prohibit competition on the grounds that it was "too risky," and therefore become an "ultra-minimal state." But at this point, it would be obligated to compensate consumers who were prohibited from purchasing competitors' services, so it would do so in kind by giving them access to its own police and legal services -- thereby becoming a minimal state. And none of these steps, according to Nozick, violates libertarian rights.
There have been literally dozens of anarchist attacks on Nozick's derivation of the minimal state. To begin with, no state arose in the manner Nozick describes, so all existing states are illegitimate and still merit abolition. Secondly, anarcho-capitalists dispute Nozick's assumption that defense is a natural monopoly, noting that the modern security guard and arbitration industries are extremely decentralized and competitive. Finally, they reject Nozick's principles of risk and compensation, charging that they lead directly to the despotism of preventive law.