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

- RT @pshenoy: Reason #21 to join @umasscs as a faculty or grad student. Great outdoor rec, including beautiful hiking trails. There is still… 3 weeks ago
- Are you finishing a great Ph.D. in CS Theory and can't imagine life without more problem solving and paper deadline… twitter.com/i/web/status/1… 1 month ago
- RT @umasscs: A team of CS, math & EE researchers—led by Andrew McGregor (@polylogblog) from #UMassCICS—was awarded a $1.5M @NSF grant to cr… 1 month ago
- Great colleagues, good coffee, active music scene, and inspiring surroundings... come and prove theorems in beautif… twitter.com/i/web/status/1… 1 month ago
- Whenever you make a conjecture, before you publicize it, take a deep breadth and count from 1 to n. Voila, there's your counter example. 2 years 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.