Downloads provided by UsageCounts
<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>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 and EXP. Whether LOGSPACE = P 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. 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. SUCCINCT-MAXIMUM is a succinct version of a P-complete problem under the complexity of properties of succinctly representable graphs. Hence, according to the Papadimitriou and Yannakakis investigation, this should be in EXP-complete and therefore, this would imply the complexity class P is not equal to NP due to the Hierarchy Theorem. Certainly, there is projection reducibility from CIRCUIT VALUE to MAXIMUM, because MAXIMUM is P-complete under logarithmic reductions and we show we can convert logarithmic reductions into projection reductions.
Complexity Classes, Polynomial Time, Complete Problem, Succinct Representation, Logarithmic Space
Complexity Classes, Polynomial Time, Complete Problem, Succinct Representation, Logarithmic Space
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
| views | 12 | |
| downloads | 9 |

Views provided by UsageCounts
Downloads provided by UsageCounts