Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaneys Theorem, with applications
80
0
0.0
(
0
)
Added by
Joshua Grochow
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Authors
Joshua A. Grochow
Ask ChatGPT about the research
No Arabic abstract
Mahaneys Theorem states that, assuming $mathsf{P} eq mathsf{NP}$, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind (Geometric sets of low information content, Theoret. Comp. Sci., 1996). This proof is so simple that it can easily be taught to undergraduates or a general graduate CS audience - not just theorists! - in about 10 minutes, which the author has done successfully several times. We also include applications of Mahaneys Theorem to fundamental questions that bright undergraduates would ask which could be used to fill the remaining hour of a lecture, as well as an application (due to Ikenmeyer, Mulmuley, and Walter, arXiv:1507.02955) to the representation theory of the symmetric group and the Geometric Complexity Theory Program. To this author, the fact that sparsity results on NP-complete sets have an application to classical questions in representation theory says that they are not only a gem of classical theoretical computer science, but indeed a gem of mathematics.
rate research
Read More
The proof of Todas celebrated theorem that the polynomial hierarchy is contained in $P^{# P}$ relies on the fact that, under mild technical conditions on the complexity class $C$, we have $exists C subset BP cdot oplus C$. More concretely, there is a randomized reduction which transforms nonempty sets and the empty set, respectively, into sets of odd or even size. The customary method is to invoke Valiants and Vaziranis randomized reduction from NP to UP, followed by amplification of the resulting success probability from $1/poly(n)$ to a constant by combining the parities of $poly(n)$ trials. Here we give a direct algebraic reduction which achieves constant success probability without the need for amplification. Our reduction is very simple, and its analysis relies on well-known properties of the Legendre symbol in finite fields.
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-paper puzzles. Viewed as a graph partitioning problem, we prove NP-completeness of partitioning a rectangular grid graph into two induced trees (normal Yin-Yang), or into two induced connected subgraphs (Yin-Yang without $2 times 2$ rule), subject to some vertices being pre-assigned to a specific tree/subgraph.
This document presents a simpler proof showcasing the NP-hardness of Familial Graph Compression.
The computational complexity of a problem arising in the context of sparse optimization is considered, namely, the projection onto the set of $k$-cosparse vectors w.r.t. some given matrix $Omeg$. It is shown that this projection problem is (strongly) NP-hard, even in the special cases in which the matrix $Omeg$ contains only ternary or bipolar coefficients. Interestingly, this is in contrast to the projection onto the set of $k$-sparse vectors, which is trivially solved by keeping only the $k$ largest coefficients.
This short note present a proof of $P eq NP$. The proof with double quotation marks is to indicate that we do not know whether the proof is correct or not.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
