I'm not sure I understand what you consider to be the difference between anarchism and anarcho-capitalism.
Here we run into the problem of semantics, and the word "anarchy" being used by different people to mean very different things. Anarcho-Capitalism (note the dash and the capitalization) is definitely
substantially different from the most popular ideas about anarchy, because it supports very strong property rights and encourages some level of social hierarchy through contractual obligations. It is a form of Capitalism, with Anarcho- being an adjective, not a noun. Some people whose ideas are identical to Anarcho-Capitalism prefer terms like "
voluntaryism" instead, but that term is even easier for other ideologies to hijack. Calling it something like "pure free market capitalism" might be an improvement, but everyone inventing their own definitions would lead to absolute chaos. So for now I'll have to bite the bullet and call myself an Anarcho-Capitalist, following in Murray Rothbard's footsteps, until my own ideas are sufficiently well defined. The good thing about this term is that it scares away both the socialists and the conservatives, so it probably will not be hijacked any time soon.
Is medieval Iceland an example of anarchism in your opinion?
It is tempting to speculate, but I won't, especially since historical nitpicking will distract from more substantive arguments for Anarcho-Capitalism. There were very few examples of
heavier-than-air flight before the 20th century, but that doesn't make it a bad idea in the present.
[...] I know that a society that does not accept NAP as a principle is doomed to fail [...]
That's not exactly true, depending on your definition of "fail". My metaphysics (evolutionary pragmatism) are built around the principle of competitive advantage, not mere survival - a society that violates Natural Rights the least will have an empirically-observable evolutionary advantage over the societies that violates them more.
A tribe of savages can exist with only the most primitive deterrents against murder and no formal concepts of liberty or property at all! Human nature is a moving target, especially if you track humanity
from the primordial goo onward. Cooperative pact behavior becomes beneficial in even pre-mammalian stages of animal development, but it doesn't evolve into a universal Right to Life as we know it today until at very least the development of language, and it was really the development of early agriculture that made it beneficial for human tribes to not kill each-other over access to the far more limited means of hunter-gatherer survival. Agriculture and writing also enable some degree of property rights, but some restrictions on human liberty remain functionally beneficial until widespread functional literacy and access to information technology can be accomplished.
A Communist culture can survive and even have sophisticated technology (of course only in the hands of the ruling elite), but what demonstrates the irrationality of Communism is how poorly it compares with other political systems that are less irrational in their understanding and defense of Natural Rights. Communism is built around a vision of humanity as it was during the industrial revolution, and though Communist countries were able to import a lot of technological ideas from the more Capitalist countries they were still unable to effectively imitate them, much less catch up in scientific and social advancement. If the more Capitalist countries didn't exist, people in Communist countries would be stuck in a dystopia similar to the one described in Ayn Rand's
Anthem, but they'd think they are doing just fine because they'd have no point of reference to tell them otherwise.
Truths can only be discovered through free experimentation and free comparison, which is why Anarcho-Capitalism is the most rational political system - it applies the scientific method to the realm of political thought, and it encompasses the ability for individuals to experiment with all other political systems by voluntary association. You can build a Communist charter city within Anarcho-Capitalism, with a 300ft statue of Stalin or whatever the heck you want, but you can only do it on legitimately acquired land and with people who choose to be there voluntarily, with their children having the right to know about the outside world and the freedom to leave if they so choose. If my knowledge about Communism is correct, then your city will fail economically as all competent people decide it is no longer in their interest to be a part of your "gift economy" and only the freeloaders remain. This intergovernmental competition and freedom of choice is the only effective weapon we have against government tyranny, and that is why the threat of a homogenizing all-powerful World Government is the sum of all fears!
[...] but it's unclear to me whether you suggest NAP as a 'divine right' or simply a practical solution for improving society as a whole.
I only used the term "divine right" to mock the alleged rights that any government claims to have to impose taxation, regulation, and so on (i.e. if you were to "tax" your neighbor yourself then that would clearly be seen as theft, but if you go through the "magical ballot box ritual" then suddenly it's a-OK). NAP is an economic concept, not much different than the law of
supply and demand - a rational compromise between billions of "greedy capitalists" who all individually want to rule the world, but know they don't stand a chance and don't want to die trying.
What is the philosophical/logical proof of taking "that socities evolve is absolutely good" as the premise?
All members of the human society exist, and they choose to exist, as material beings living in a material universe. (People who don't like the immutable natural laws of the universe they were born into are free to kill themselves at any time.) The reality of human existence requires certain empirically-verifiable universal rules of human behavior, many of which were recognized to some degree by the less savage of the ancient civilizations
for thousands of years, and have been a prerequisite for you ever being born. It is functionally impossible for cavemen who refuse to recognize the Right to Life for anyone outside their immediate tribal group, much less their Rights to Liberty and Property, to effectively domesticate animals, till the soil, irrigate the Nile delta, drain the swamps of Europe turning infertile land fertile, reduce infant mortality, establish global trade, build electric power plants, mine silicon, and do all of the other things that make the survival of 7 billion people on this planet possible. (And this would be even more self-evident as humanity begins to expand beyond this planet.) That is the only objective basis for a "social contract", which you are obligated to follow even though you never signed it - you don't have to be a nice guy, and you don't have to bow down to anyone, but you do have to live within the empirically-verifiable economic constraints that make your existence possible.
What if someone argues that they want socities to revert back to the stone age?
You cannot make the human civilization at large revert to the stone age without violating the rights of every person who disagrees with you (hopefully everyone), but you are free to set up your own "stone age community" on privately owned land, or a seastead, or a space station, or a terraformed moon on the other side of the galaxy, etc - just as long as all adults are there through individual consent, and the children have the right to leave if/when they so choose. My system will be backed by the vast majority of humanity who value their life and the well-being of their children, and recognize that life in the stone age was nasty, brutish, and short. Your system will be backed by the people who want to sacrifice all benefits of civilization (including a chance at life extension technology and eventual immortality in a Holodeck heaven that is infinitely better than whatever delusions our forefathers fantasized about), or rather the fraction of such people who don't just want to hang out in a voluntary community as I mentioned. If the proponents of my system still fail to convince all proponents of your system to not initiate aggression (and some people simply cannot be reasoned with) then my system will be able to protect itself through defensive force.