Ely asked me to remind everyone that the deadline for the 26th Annual Symposium on Combinatorial Pattern Matching is fast approaching. You have until 2nd February to match your combinatorial pattern.

### About

A research blog about data streams and related topics.

### Author

### Recently Tweeted

- Looking to hire a postdoc in data stream algorithms, sublinear algorithms, or trace reconstruction (or some tangent… twitter.com/i/web/status/1… 3 weeks ago
- The NSF-sponsored UMass TRIPODS Institute for Theoretical Foundations of Data Science is offering an REU Program. S… twitter.com/i/web/status/1… 2 months ago
- I appreciate the candor of the error message "LaTeX Error: Float(s) lost" but lose one float, shame on you, lose tw… twitter.com/i/web/status/1… 9 months ago
- For anyone interested, our paper will be presented at ICML 2020. twitter.com/yudapearl/stat… 11 months ago
- RT @sigmod: The 2020 ACM PODS Alberto. O. Mendelzon Test-of-Time Award is awarded to Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau an… 11 months ago

### Blogroll

- 0xDE
- A CS Professor's blog
- Algorithmic Game Theory
- Computational Complexity
- Computing Research Policy
- Ernie's 3D Pancakes
- Gödel's Lost Letter and P=NP
- in theory
- Machine Learning (Theory)
- My Biased Coin
- my slice of pizza
- Nuit Blanche
- Oddly Shaped Pegs
- Property Testing Review
- Shtetl-Optimized
- Silent Glen Speaks
- Stack Exchange
- The Geomblog
- Vanity of Vanities, all is Vanity
- WebDiarios de Motocicleta
- Windows on Theory

### UMass CS Blogs

### Recent Posts

### Categories

- accepted papers (13)
- announcements (2)
- conference report (19)
- educational (10)
- open problems (4)
- Uncategorized (15)

### Recent Comments

- Eldon on Open Problems in Communication Complexity
- vegafrank on CPM 2015
- vegafrank on CPM 2015
- web agency on Sublinear Algorithms: Day 2a
- Jelani on Bite-sized streams: CR-Precis
- Jelani on Bite-sized streams: CR-Precis
- Paul on Students!
- Paul on Students!
- bistaumanga on Bite-sized streams: Exact Median of a Random-Order Stream
- European IT Distribution on Slides from Workshop on Distributed and Streaming Data
- Frank Vega on Students!
- Best Computer Science Blogs of 2012 on Data Streaming in Dortmund: Day 1
- He on Announcing Sublinear.Info!
- Krzysztof on Announcing Sublinear.Info!
- Andrew on Announcing Sublinear.Info!

### Archives

- April 2017 (1)
- January 2015 (1)
- December 2013 (1)
- September 2013 (1)
- May 2013 (1)
- March 2013 (1)
- December 2012 (1)
- October 2012 (1)
- July 2012 (2)
- June 2012 (1)
- May 2012 (3)
- April 2012 (4)
- March 2012 (1)
- September 2011 (1)
- August 2011 (1)
- June 2011 (4)
- May 2011 (7)
- February 2011 (1)
- December 2010 (1)
- October 2010 (1)
- September 2010 (3)
- August 2010 (1)
- July 2010 (3)
- June 2010 (2)
- April 2010 (1)
- March 2010 (2)
- February 2010 (4)
- December 2009 (2)
- November 2009 (2)
- October 2009 (2)
- September 2009 (3)
- August 2009 (1)
- July 2009 (1)
- May 2009 (1)

## 2 comments

Comments feed for this article

December 1, 2015 at 5:28 pm

vegafrankWHAT IF P = NP?

We define an interesting problem called $MAS$. We show $MAS$ is actually a succinct version of the well known $\textit{NP–complete}$ problem $\textit{SUBSET–PRODUCT}$. When we accept or reject the succinct instances of $MAS$, then we are accepting or rejecting the equivalent and large instances of $\textit{SUBSET–PRODUCT}$. Moreover, we show $MAS \in \textit{NP–complete}$.

In our proof we start assuming that $P = NP$. But, if $P = NP$, then $MAS$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, because they are $\textit{NP–complete}$. A succinct version of a problem that is complete for $P$ can be shown not to lie in $P$, because it will be complete for $EXP$. Indeed, in Papadimitriou’s book is proved the following statement: “$NEXP$ and $EXP$ are nothing else but $P$ and $NP$ on exponentially more succinct input”. Since $MAS$ is a succinct version of $\textit{SUBSET–PRODUCT}$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, then we obtain that $MAS$ should be also in $\textit{EXP–complete}$.

Since the classes $P$ and $EXP$ are closed under reductions, and $MAS$ is complete for both $P$ and $EXP$, then we could state that $P = EXP$. However, as result of Hierarchy Theorem the class $P$ cannot be equal to $EXP$. To sum up, we obtain a contradiction under the assumption that $P = NP$, and thus, we can claim that $P \neq NP$ as a direct consequence of the Reductio ad absurdum rule.

You could see more on…

https://hal.archives-ouvertes.fr/hal-01233924/document

Best Regards,

Frank.

December 18, 2015 at 5:16 pm

vegafrankTHE P VERSUS NP PROBLEM

We define an interesting problem called $MAS$. We show $MAS$ is actually a succinct version of the well known $\textit{NP–complete}$ problem $\textit{SUBSET–PRODUCT}$. When we accept or reject the succinct instances of $MAS$, then we are accepting or rejecting the equivalent and large instances of $\textit{SUBSET–PRODUCT}$. Moreover, we show $MAS \in \textit{NP–complete}$.

In our proof we start assuming that $P = NP$. But, if $P = NP$, then $MAS$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, because all currently known $\textit{NP–complete}$ are $\textit{NP–complete}$ under logarithmic-space reduction including our new problem $MAS$. A succinct version of a problem that is complete for $P$ can be shown not to lie in $P$, because it will be complete for $EXP$. Indeed, in Papadimitriou’s book is proved the following statement: “$NEXP$ and $EXP$ are nothing else but $P$ and $NP$ on exponentially more succinct input”. Since $MAS$ is a succinct version of $\textit{SUBSET–PRODUCT}$ and $\textit{SUBSET–PRODUCT}$ would be in $\textit{P–complete}$, then we obtain that $MAS$ should be also in $\textit{EXP–complete}$.

Since the classes $P$ and $EXP$ are closed under reductions, and $MAS$ is complete for both $P$ and $EXP$, then we could state that $P = EXP$. However, as result of Hierarchy Theorem the class $P$ cannot be equal to $EXP$. To sum up, we obtain a contradiction under the assumption that $P = NP$, and thus, we can claim that $P \neq NP$ as a direct consequence of the Reductio ad absurdum rule.

You could see more on (version 3)…

https://drive.google.com/file/d/0B3yzKiZO_NmWZ1M1MkNuYVBreXc/view?usp=sharing

Best Regards,

Frank.