I am an undergrad student that likes to study approaches to settle $P$ vs $NP$. I know that there is GCT method, and another way is to attack it by logic equivalent. I am a double major student in CS and math, sadly i did not study logic well but i studied group theory, rings and module. As far as i did research i know to understand GCT u need to know about category theory, representation theory and algebraic geometry. But i really do not know which books are the best to study and understand GCT in the best way possible.
I really appreciate if some one could help me pick some good books toward GCT and read them by appropriate order. For GCT i picked alegbra chapter 0 by Paolo Aluffi, Algebra: A Graduate Course by Martin Isaacs and Patrick Morandi, Field and Galois Theory. i could not understand which book is good for representation theory.
On the other hand sadly i did not study logic very well so i decided to study it again to understand equivalent of $P$ vs $NP$ , what advances do we have on this part? which books are good for this perspective? For I picked Logic and Structure by Dirk Dalen to start again. But i am not sure which book i should continue to read after this book.
Sorry if my question is very vague but in short i want to understand the latest research in GCT and logical equivalent of $P$ vs $NP$; which books could help me?
In terms of GCT, there are two references I like:
In my opinion, GCT is not an accessible area. So while these resources are relatively good, don't be discouraged if you find them to be tough-going.
In terms of logic, you really don't need much beyond your Intro to Proofs course unless you are looking closely at Descriptive Complexity Theory. For Descriptive Complexity, the following references are standard:
In order to attack P vs. NP, we want to look for natural techniques to try.
One perspective on Structural Complexity Theory is that it is Computability + Resource Constraints. In this vein, we ask whether Computability techniques will be useful in resolving P vs. NP. Unfortunately, the answer is no. Most Computability techniques relativize (are not sensitive to the presence of oracles). On the other hand, the P vs. NP problem does not relativize- this is the Baker-Gill-Solovay result from 1975. There are oracles $A, B$ s.t. $\textsf{P}^{A} = \textsf{NP}^{A}$ and $\textsf{P}^{B} \neq \textsf{NP}^{B}$. We may take $A = \textsf{PSPACE}$, while we can construct $B$ via a diagonalization argument.
Turing Machines are equivalent to circuits via simulation arguments. In this vein, we ask whether techniques from Circuit Complexity can be leveraged to resolve P vs. NP. Key techniques involve Fourier analysis of the combinatorics of the circuits. The Razborov-Rudich Natural Proofs Barrier effectively rules out such techniques.
A technique that is useful in both Interactive Proofs and Circuit Complexity is called arithmetization. That is, we encode Boolean formulas as polynomials and analyze the properties of those polynomials (usually, the fact that they are low-degree). The Aaronson-Widgerson Algebrization barrier rules out arithmetization on its own, as well as in tandem with diagonlization.
The GCT program is not known to be a viable path to resolving P vs. NP or other major open questions in Complexity Theory. Rather, we don't know that it won't work. There are (to the best of my knowledge) no known barriers regarding GCT.
Edit: There are folks who look at Descriptive Complexity (see for instance, the works of Neil Immerman, Martin Grohe, Pascal Schweitzer, and their students). The goal is to give logical characterizations of complexity classes, or really to give logical characterizations of resource-bounded computation (e.g., poly-time computation) on specified families of relational structures (e.g., graphs). In other words, Descriptive Complexity is closely tied to Isomorphism Testing.
A (the) primary tool to analyze these logics are Ehrenfeucht--Fraisse pebble games. There are two players: Spoiler and Duplicator. Spoiler's goal is to show that two structures are inequivalent (e.g., two graphs are non-isomorphic), and Duplicator's goal is to match (or duplicate) the structure that Spoiler points out. To separate out two logics, we need (i) an infinite family $\{ (G_{n}, H_{n}) \}$ where $G_{n} \not \cong H_{n}$, (ii) a proof that Duplicator has a winning strategy on $G_{n}$ and $H_{n}$ for Logic A, and (iii) a proof that Spoiler has a winning strategy in the corresponding game for Logic B.
While I am not aware of formal barriers like in P vs. NP, separating logics is hard for the same reason as separating complexity classes.
It's also worth pointing out that problems like deciding a winner in the Ehrenfeucht-Fraisse games and model checking are computationally hard problems, with precise lower bounds (e.g., $\textsf{PSPACE}$-complete in some cases- https://link.springer.com/chapter/10.1007/10703163_11). The case of $\textsf{FO} + \textsf{LFP} + \textsf{C}$ is nice b/c there is a poly-time algorithm for these problems: Weisfeiler--Leman. Sandra Kiefer's thesis provides an excellent survey of Weisfeiler--Leman (https://publications.rwth-aachen.de/record/785831).