A central question in Computer Science is problem solvability by deterministic algorithms, that is, guaranteed to yield an exact solution within a finite and reasonable time while using finite and reasonable resources. The set of all problems admitting such "computable" algorithms is denoted by P. The set of all problems which do not admit such deterministic solution are denoted by NP.
NP problems are further divided between problems which allow easy verification of a proposed solution and those which do not. The former can be solved by trial and error approaches based on "guessing" succesive solutions and evaluating them for accuracy or fit. This class of problems is referred to as NP-complete class. The second group is referred to as the NP-hard class. A very big and unsolved question is "is N=NP ?" (posed since 1971). There is, at present, a million dollar prize available to anybody who comes up with a correct proof that either P!=NP (P is not the same set as NP) or its converse. This is not just an esoteric speculation since, as we shall see below, a great many significant consequences fall out from it. Basically if N=NP all problems would admit a robotized or computerized perfect solution.
A clear tutorial on the N=NP question & issues of computational complexity can be found at:
Scott Aaronson proposes ten arguments why N!=NP is likely to be true. particularly insightful is his 9th argument:
"If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It's possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn't we already have evolved to take advantage of it? (Indeed, this is an argument not only for P!=NP, but for NP-complete problems not being efficiently solvable in the physical world.)"
Scott Aaronson also edits the Complexity Zoo Blog.
The relevance of computational complexity theory to the NDD is based on two main considerations:
Some relevant information about the inherent intractability of DAG based processes is given by the following references:
Constructing a minimal DAG is shown to be NP-complete in the following paper. which supplies a novel multi-step algorithm for constructing a small sized DAG:
Scheduling computational resources over a set of tasks which are represented by a directed acyclic graph (DAG) called a "task graph", has been known to be strong NP-hard intractable:
We have seen in NDD that embryogenesis processes are DAG based. Therefore the above computability results have significant implications for them. In particular: