P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? A precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Given a positive integer x and a collection S of positive integers, MAXIMUM is the problem of deciding whether x is the maximum of S. We prove this problem is complete for P. Another major complexity classes are LOGSPACE, NLOGSPACE, coNP and EXP. Whether LOGSPACE = NLOGSPACE is a fundamental question that it is as important as it is unresolved. We show the problem MAXIMUM can be decided in logarithmic space. Consequently, we demonstrate the complexity class LOGSPACE is equal to P and thus, LOGSPACE is equal to NLOGSPACE. Furthermore, we define a problem called SUCCINCT-MAXIMUM. SUCCINCT-MAXIMUM contains the instances of MAXIMUM that can be represented by an exponentially more succinct way. We show this succinct version of MAXIMUM is in P under the assumption of P = NP. Since SUCCINCT-MAXIMUM is a succinct version of a P-complete problem under the complexity of properties of succinctly representable graphs, then this might be a good candidate to be in EXP-complete and therefore, this would imply the complexity class P is not equal to NP as a consequence of the Hierarchy Theorem.
closed as off-topic by Jan Johannsen, Aryeh, Gamow, Emil Jeřábek, Hsien-Chih Chang 張顯之 Jan 10 at 19:04
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Aryeh, Gamow, Emil Jeřábek