Theory of Computation and Complexity Theory

[joaogui]

There are no books about computation models and complexity theory.

If there is no space for many books I suggest these four:

• Introduction to the Theory of Computation by Sipser: an undergrad introduction to the Theory of Computation.
• Computational Complexity: A Modern Approach by Arora and Barak: a more advanced (grad) book about Complexity Theory covering many theorems and topics.
• The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine by Petzold: what the title says. It also gives some context about the paper and a little bit about Turing's life.
• Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johsnon: a catalog of NP-Complete problems.

All of them are self-contained with sections or appendices covering the basics. They could be added to the "Fundamentals of computing and the Internet" section or the "Algorithms and data structures" section.

[prateekrastogi]

As the inventor of "Space-Time Complexity" and its implications for Quantum Computing Performance Measurements, my organization repo was not even included. Hoping for it to be in archive in next snapshot.

[prateekrastogi]

Also, I have mathematically proved P=NP

[rezendi]

@joaogui Thanks for this; will address, and will close this issue when the TT is edited accordingly.

[prateekrastogi]

Transfinite P = Transfinite NP. Afterwards, using axiom of choice, P=NP.

Since your computational complexity is derived from monotone functions of taking a positive integer n, in "On the Computational Complexity of Algorithms" by Juris Hartmanis and Richard E. Stearns, which laid out the definitions of time complexity and space complexity while using conceptualizations of "Set" in original paper, so as per as Set Theory laid out by Georg Cantor, the father of Set Theory, which himself defined "axiom of choice" while defining set theory and introduced notion of Transfinite Cardinals for Bijective Infinite Sets.

Therefore, either basis of computational complexity is wrong or set theory is wrong. Else P=NP ;-)

[prateekrastogi]

Here is the wiki relevant abstract:

"In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite sets. Cardinality is defined in terms of bijective functions. Two sets have the same cardinality if, and only if, there is a one-to-one correspondence (bijection) between the elements of the two sets. It is also possible for a proper subset of an infinite set to have the same cardinality as the original set, something that cannot happen with proper subsets of finite sets."

Cardinality is studied for its own sake as part of set theory. It is also a tool used in branches of mathematics including model theory, combinatorics, abstract algebra, and mathematical analysis. In category theory, read reactive functional programming, the cardinal numbers form a skeleton of the category of sets. Here's wiki links for those interested:

• https://en.wikipedia.org/wiki/Cardinal_number

• https://en.wikipedia.org/wiki/Cardinality

• https://en.wikipedia.org/wiki/Axiom_of_choice

[ghost]

@prateekrastogi You are mathematically correct, but this won't save it from being lost forever in dungeon.

[rezendi]

Added Introduction to the Theory of Computation. I don't think we'll really need more than this for the Tech Tree, which is intended primarily as a compilation of more practical guides.