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.

Advertisements

January 22, 2015 in Uncategorized

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.

Advertisements

A research blog about data streams and related topics.

- 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 weeks ago
- UMass CS hiring in theory at the assistant/associate level. cics.umass.edu/job/assistanta… 2 weeks ago
- RT @dagstuhl: Today @dagstuhl: Theory and Applications of Hashing dagstuhl.de/17181 -- M.Mitzenmacher, R.Pagh, D.Woodruff, M.Dietzfel… 5 months ago
- RT @boydgraber: My student Mohit (co-advised with @haldaume3) will be joining UMass in Fall 2018 (after postdoc to be named). @Students, go… 5 months ago
- RT @umdclip: Great news: @umdcs and @umdclip PhD student Mohit Iyyer will join @umasscs as an Assistant Prof in Fall 2018! Congratulations… 5 months ago

- 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

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

- 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!
- Amit Chakrabarti on Announcing Sublinear.Info!

- 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)

Blog at WordPress.com.Ben Eastaugh and Chris Sternal-Johnson.

%d bloggers like this:

## 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.