2011/10/02 by Koji Kobayashi, Kobayashi, Koji
Computer Science · Decision Sciences · Engineering · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Manufacturing Process and Optimization #Model-Driven Software Engineering Techniques #Resource-Constrained Project Scheduling #cs.CC
paper · pdf · doi:10.48550/arxiv.1110.0200
7 pages, in English and Japanese
openalex publication_date 2011/10/02 · arxiv created 2011/11/21 · arxiv updated 2011/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper talk about that NP is not AL and P, P is not NC, NC is not NL, and NL is not L. The point about this paper is the depend relation of the problem that need other problem's result to compute it. I show the structure of depend relation that could divide each complexity classes.