P Complete Problem with Circuit and Monotone Circuit and Np Completeness Peoblem with Satisfiability and 3-Coloring

NP Complete (truncated as NPC) problems, remaining at the core of choosing whether P=NP, are among hardest problems in computer science and other related areas. Through decades, NPC problems are treated as one class. Seeing that NPC problems have various natures, it is impossible that they will have a similar complexity. Our escalated investigation demonstrates that NPC problems are not all equivalent in computational complexity, and they can be additionally classified. In most of this course, we will look at the asymptotic complexity of problems. As opposed to considering, express, the time required to solve 3-coloring on graphs with 10; 000 nodes on some particular model of computation, we will ask what is the best asymptotic running time of an algorithm that solves 3-coloring on all instances. Surely, we will be significantly less ambitious, and we will basically ask whether there is a \feasible" asymptotic algorithm for 3-coloring.