One comment I'd like to make is that one shouldn't confuse asymptotic complexity with practical complexity. It's possible for a problem to be NP-complete but still be easy to solve for all but extremely large cases. I realize you haven't made this mistake - it's just something that could trip up someone less familiar with this kind of reasoning.

Additionally, it seems many of your arguments would also equally apply to current narrow AI systems like search, object recognition, playing chess, and so on. Yet systems like these have been constructed. What special property does "what humans do" have that distinguishes it from these narrow AI systems? (Note that I'm not saying such a special property doesn't exist, I'm just saying it's not clear, through your arguments, what it is).

Kolmogorov complexity is not (closely) related to NP completeness. Random sequences maximize Kolmogorov complexity but are trivial to produce. 3-SAT solvers have tiny Kolmogorov complexity despite their exponential worst case performance.

I also object to thinking of intelligence as "being NP-Complete", unless you mean that incremental improvements in intelligence should take longer and longer (growing at a super-polynomial rate). When talking about achieving a fixed level of intelligence, complexity theory is a bad analogy. Kolmogorov complexity is also a bad analogy here because we want any solution, not the shortest solution.

This seems to conflict with the most intuitive location of the intelligence hard step: somewhere between chimp and human.

Chimpanzees seem to exhibit human traits such as self awareness, theory of mind, appreciation of beauty, language, problem solving, vendettas and so forth. I would think the hard step would be earlier than this. (and AlexMennen's comment throws more doubt on this).

If this circumstance doesn't change, the first government to try will be an authoritarian one like China. Such a government will ensure the resulting superhumans will have extreme built-in loyalty*, resulting in a world-wide superdictatorship.

I don't think China is a dictatorship, because its the Chinese communist party in charge, rather than one specific individual. This isn't just argument over semantics - while China is comparatively authoritarian, there isn't a single point of failure, one person with absolute power who can go insane and wreck the country.

Therefore, the highest priority seems to be changing culture in a way that will ensure a supportive public opinion for a future friendly superintelligence project.

Or, pursuing a form of government which is neither a dictatorship nor a democracy. I previously advocated the replacement of elections with examinations.

Evolution only had to get it right once, so in an infinite universe, anthropic selection, etc. This overlooks a more significant fact: ontogeny gets it right over and over again, regularly, predictably, reproducibly. Somehow, starting from just a few tens of thousands of genes and their cellular support structures, in which no intelligence is discernable, brains develop that respond to the environment around them by organising themselves into thinking beings. The same thing happens on a lesser scale with the chimpanzees, and dogs, and even insects.

How does it happen? Nobody knows. That the mechanism has been brought into existence at all can be an anthropically selected fluke, but once it exists, how it works is not a fluke but a repeatable process.

Reverse engineer the process, and you will be well on the way to creating an AGI.

ETA: It occurs to me that I don't know how often evolution has invented neurons. Just once, or more than that? It's certainly invented eyes more than once.

A way to test your theory is to take a smart creature whose common ancestor with mankind was stupid and see if we could put human level or above intelligence into it by, say, minor gene changes or eliminating its mutational load..

Have you read this paper by Shulman and Bostrom?

I generally agree that computational complexity is probably relevant to the problem of AGI, but I can see several problems in your arguments:

There are several arguments the AGI problem is of a similar "flavor" to problems that are NP-complete.

Many proposed AI algorithms solve problems which are NP-hard (or worse, PSPACE-hard) in the general case. Keep in mind however, that NP-hardness and related notions are part of worst-case complexity theory, while average-complexity w.r.t. some appropriate class of "natural" problem distributions is relevant for AI and AGI. The relationship between worst-case complexity and average-complexity is poorly understood in the general case, and what would constitute a "natural" problem distribution is even less understood.

Similarly, Goedel incompleteness means there is no single algorithm for proving all provable theorems.

No. You can prove all provable theorems by just enumerating and checking all candidate proofs. Gödel's incompleteness theorem states that there are certain statements which are "true" (in a suitable technical sense which intuitively boils down to the fact that you will never be able to find a counterexample) but are unprovable, unless arithmetic in inconsistent.

It feels like there is a principle of mathematics which rules out algorithms that are "too good to be true": a single "magic wand" to solve all problems. In a similar way, AGI is a "magic wand": it solves "all" problems because you can simply delegate them to the AGI.

It can be true that "magic wand" algorithms can't exist because of complexity issues, but this would not be an issue for a humal-level AGI since humans aren't "magic wands". A strongly super-human AGI would be much more like a "magic wand" and I would agree that the theoretical and practical possibility of this kind of intelligence is much more speculative.

Another argument has to do with Solomonoff induction.

I think that Solomonoff induction and the intelligence metrics based on it, even with the inclusion of resource penalties a la Levin complexity, are too strong and don't accurately capture the notion of effectively physically realizable intelligence.

Consider the bit sequence generated by a strong stream chiper with an (uniformly sampled) key. It has a very small Levin complexity, but, as per the one-way function conjecture we don't expect any AI to be ever able to efficiently predict it, as it would amount to breaking the chiper.
And yet, according to intelligence metrics based on Kolmogorov or Levin complexity, a smart AI should easily solve this problem.

It seems plausible that AGI theory has failed to produce practical algorithms so far is that because it use definitions of algorithmic complexity which are too coarse and classify as easy problems which are in fact very hard. That's why I think that a better understanding of complexity is probably relevant for AGI research, but given the current state of knowledge, I don't see complexity issues as fundamentally dooming the field.

Before the hard step, an early version E1 of E co-evolves with a module h which performs a similar function to H but does it much worse (imagine a rough heuristic which works for many of the cases in a relatively narrow domain). During the hard step, H appears "out of the blue" due to sheer anthropic luck after which the E1-h "wire" is replaced by an E1-H wire. After the hard step, natural selection proceeds to transform E1 into its final version E2. This picture seems to be consistent with hard step happening to our chimp-like ancestor after which natural selection rapidly transformed the result into homo sapiens sapiens.

So your claim is that going from, say, worm to chimp is relatively easy while going from chimp to human is hard and can be only accomplished by anthropic brute forcing.

This should imply that replicating the level of intelligence of a chimp should be relatively easy, while replicating what sets apart humans from chimps should be hard. This is inconsistent with current achievements in narrow-AI/operations research:
Playing chess, playing Jeopardy, betting on the stock market, placing and routing a network of components in an electric grid, or a network of computers, or an integrated circuit, scheduling logistics for a large company or government agency, etc., are all things that chimps can't do at all, human without computers can do with some difficulty, and narrow-AIs can do better than humans.
On the other hand, visual object recognition in an unstructured environment like a jungle, precise 3D dynamic motion control using limbs, general planning in an unstructured environment full of uncertainty, non-eusocial coordination with other competitive agents enabling the formation of effective groups with cheater detection and punishment mechanics and non-trivial politics, are all things that wolves can do, chimps can do, humans can do but narrow-AIs can't do yet.
This suggests that worm-to-chimp cognitive abilities are harder, or at least it is harder to find effective algorithms for them, than chimp-to-human cognitive abilities.

EDIT:

If I have to guess, I would say that what sets humans apart from chimps is that humans became able to perform general-purpose computing: our brains are equipped with a sort of "universal Turing machine", except that it is not only very slow but it has also a very short tape and it is very noisy. Yet, it works well enough that, in combination with all the other heuristic and domain-specific modules in our brain, it allows us to perform complex cognitive tasks that other animals can't do.
The fact that (AFAIK) all human languages are able to express abstract thoughts and in particular meta statements about thinking and language itself, is evidence of this fact, and it is probably also the machinery on which this general-purpose computation is implemented in our brains.

The problem with AGI is that researchers are trying to build a human-like intelligence exactly backwards compared with how evolution did: digital electronics allows us to build excellent general-purpose computers, much better than the one embedded in the human brain, but they lack all the domain-specific heuristic modules that humans acquired over million years of evolution. That's why, IMO, narrow-AI succeeds at hard, human-only cognitive tasks and fails at the kind of things that a dog does instinctively.

I have doubts regarding this:

It feels like there is a principle of mathematics which rules out algorithms that are "too good to be true": a single "magic wand" to solve all problems. In a similar way, AGI is a "magic wand": it solves "all" problems because you can simply delegate them to the AGI.

It seems to me that either human-level GI is impossible or it is not. But, we humans constitute an existence proof that it is not impossible. Therefore, Gödel does not apply; clearly human-level GI is not "too good to be true". And, Gödel's incompleteness theorems really have nothing to do with how hard it might be to come up with a solution to a computable problem.

I also have doubts regarding this:

This way the AGI design problem becomes an optimization problem: find a program with an intelligence metric as high as possible. The NP-connection now suggests the following conjecture: the AGI optimization program is of exponential complexity in program length. Of course we don't necessarily need the best program of a given length...

The bold portion of the above section is key - there are various NP-hard optimization problems for which good approximate solutions can be found in polynomial time. Since human or super-human AGI does not require a maximally intelligent program, even if you could show that the AGI optimization problem is NP-hard that would say nothing about the difficulty of finding a human or super-human level AGI.

I'm not very convinced. Relatively simple heuristics can perform very well on NP-complete problems. Machine learning methods can learn very accurate models of data, without doing Solomonoff induction.

I don't see any reason to believe an enormous amount of complexity is required to reach human abilities on these tasks.

Goedel incompleteness means there is no single algorithm for proving all provable theorems.

Are you sure you meant to say that? There is such an algorithm: enumerate all proofs. What doesn't exist is an algorithm for finding a proof if one exists and reporting the nonexistence of a proof if it doesn't.

Intelligence doesn't operate on the basis of proving things. Intelligence operates on the basis of heuristics and so I find the parallel to NP-complete problems flawed.

For clarity, consider a human from 50,000 years ago and see if the way his intelligence operates has resemblance to solving problems in an NP-complete domain.

I feel you should give a strict definition of general intelligence (artificial or not). If you define it as "an intelligence that can solve all solvable problems with constrained resources", it's not clear that that humans have a general intelligence. (For instance, you yourself argue that humans might be unable to solve the problem of creating AGI.) But if humans don't have a general intelligence, then creating an artificial human-level intelligence might be easier than creating an AGI.

As well known, in scenarios with hard steps that are overcome anthropically, the hard steps are expected to be distributed on the timeline approximately uniformly. This seems to conflict with the most intuitive location of the intelligence hard step: somewhere between chimp and human.

This is basically the Doomsday problem. Any of its proposed resolutions would solve this problem and let us place a single hard (i.e. evolutionarily unlikely) step in our recent history.

This earlier thread touched on some related issues.