User mhum - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T02:49:02Z http://mathoverflow.net/feeds/user/9840 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78635/p-vs-np-and-owfs/78643#78643 Answer by mhum for P vs NP and OWFS mhum 2011-10-20T04:22:51Z 2011-10-20T17:19:41Z <p>P != NP does not imply anything about the existence of one-way functions. From Goldwasser and Bellare's "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.140.9755&amp;rep=rep1&amp;type=pdf" rel="nofollow">Lecture Notes on Cryptography</a>":</p> <blockquote> <p>However, the above mentioned necessary condition (e.g.: P != NP) is not a sufficient one. P != NP only implies that the encryption scheme is hard to break in the worst case. It does not rule-out the possibility that the encryption scheme is easy to break in almost all cases. In fact, one can easily construct "encryption schemes" for which the breaking problem is NP-complete and yet there exist an efficient breaking algorithm that succeeds on 99% of the cases. Hence, worse-case hardness is a poor measure of security.</p> </blockquote> <p>Also, two of <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.7245&amp;rep=rep1&amp;type=pdf" rel="nofollow">Impagliazzo's worlds</a> where P != NP, Heuristica and Pessiland, have no one-way functions while two others, Minicrypt and Cryptomania, do.</p> http://mathoverflow.net/questions/76254/what-is-so-plactic-about-the-plactic-monoid/76396#76396 Answer by mhum for What is so "plactic" about the plactic monoid? mhum 2011-09-26T07:50:41Z 2011-09-26T08:07:16Z <p>You can find the original Lascoux &amp; Schützenberger paper <a href="http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1981-1PlaxiqueNaples.pdf" rel="nofollow">here</a>. My French (especially mathematical French) is not great, so I haven't been able to determine how the term "<em>plaxique</em>" comes in. However, I can observe that L&amp;S first introduce <em>la congruence plaxique</em> and define <em>le monoïde plaxique</em> as the quotient of the free monoid over the congruence. So, it seems to me that they were really thinking of the congruence as plactic/plaxic more than the monoid itself (perhaps a fine distinction?). They highlight the relevant properties of the congruence in Proposition 2.5, so maybe that provides a clue?</p> <p>EDITED TO ADD: A quick scan of the OED yields no results for either "plactic" or "plaxic", but there is one result for the Latin "<em>plaxus</em>" under the etymology for the obsolete word "plash" (To bend down and interweave (stems partly cut through, branches, and twigs) so as to form a hedge or fence.):</p> <blockquote> <p>an unattested post-classical Latin form *plaxus , alteration of classical Latin <em>plexus</em> , past participle of <em>plectere</em> to plait, interweave, twine (see plexus n.)</p> </blockquote> <p>So, perhaps "<em>plaxique</em>" is meant to invoke a sense of intertwining or weaving? I could see how that could apply to the congruence relation. </p> <p>Bonus fun fact: Plaxico Burress makes an appearance in the OED in a citation for the entry "return date":</p> <blockquote> <p>New York Giants star receiver and gun nut Plaxico Burress breezed in and out of Manhattan Criminal Court in 15 minutes yesterday, with little happening besides the setting of a June 15 return date.</p> </blockquote> http://mathoverflow.net/questions/69967/titles-composed-entirely-of-math-symbols/69996#69996 Answer by mhum for Titles composed entirely of math symbols mhum 2011-07-11T07:23:39Z 2011-07-11T07:23:39Z <p>Would <a href="http://dl.acm.org/citation.cfm?id=146609&amp;CFID=31867723&amp;CFTOKEN=95840967" rel="nofollow">IP=PSPACE</a> count?</p> http://mathoverflow.net/questions/55885/why-semigroups-could-be-important/55892#55892 Answer by mhum for Why semigroups could be important? mhum 2011-02-18T18:49:13Z 2011-02-18T18:49:13Z <p>Semigroups provide a fundamental, algebraic tool in the analysis of regular languages and finite automata. <a href="http://www.liafa.jussieu.fr/~jep/PDF/HandBook.pdf" rel="nofollow">This book chapter (pdf)</a> by J-E Pin gives a brief overview of this area. </p> http://mathoverflow.net/questions/43070/hubbiness-of-a-graph/43094#43094 Answer by mhum for Hubbiness of a graph mhum 2010-10-21T20:54:35Z 2011-02-01T19:24:26Z <p>Here are some concepts that might be helpful to you:</p> <ol> <li><p>A vertex $v$ of a connected graph $G$ is an <em>articulation point</em> if the removal of $v$ from $G$ causes $G$ to be disconnected. My interpretation is that an articulation point corresponds to a "hub". This may or may not match your intuition. On the one hand, the center vertex in a star is an articulation point, but then so is any interior point in a path.</p></li> <li><p>A connected graph $G$ is <em>biconnected</em> if it does not contain any articulation points (i.e.: the removal of any single vertex from $G$ does not disconnect $G$). By convention, the graph consisting of just two vertices and one edge is considered biconnected.</p></li> <li><p>A <em>biconnected component</em> of a graph $G$ is a maximal, biconnected subgraph.</p></li> <li><p>Finally, we can define the <em>block tree</em> $BT(G)$ of a connected graph $G$ as follows: The vertices of $BT(G)$ are the biconnected components of $G$ and an edge $(u,v)$ exists in $BT(G)$ iff the biconnected components corresponding to $u$ and $v$ share a vertex (in $G$). <a href="http://en.wikipedia.org/wiki/Block_tree" rel="nofollow">This Wikipedia article</a> has a nice illustration of this concept and a description of an algorithm for constructing the block tree.</p></li> </ol> <p>I would suggest that the degree of "hubbiness" of a graph $G$ is related to the size of $BT(G)$. Let $G$ be a graph with $n$ vertices. Then:</p> <ul> <li>If $G$ is biconnected, then $|BT(G)| = 1$</li> <li>If $G$ is a star, then $|BT(G)| = n$</li> <li>If $G$ is a path, then $|BT(G)| = n-2$</li> <li>In general, if $G$ is a tree, then$|BT(G)|$ equals the number of interior vertices</li> </ul> http://mathoverflow.net/questions/52671/number-of-muti-indices-of-a-fixed-order-which-are-less-than-a-given-multi-index/52787#52787 Answer by mhum for number of muti-indices of a fixed order which are less than a given multi-index mhum 2011-01-21T19:54:51Z 2011-01-21T19:54:51Z <p>Expanding my comment into a full answer:</p> <p>By inspection, we can see that $C(n,s,p)$ is the coefficient of $x^s$ in:</p> <p>$(1 + x + x^2 + \cdots + x^{p_1}) (1 + x + x^2 + \cdots + x^{p_2}) \cdots (1 + x + x^2 + \cdots + x^{p_n})$ </p> <p>$= \Pi_{j=1}^n \Sigma_{i=0}^{p_j} x^i$</p> <p>$= \Pi_{j=1}^n {{(x^{p_j+1}-1)}\over{(x-1)}}$</p> <p>I'm not particularly expert at generating functions, so I haven't been able to reduce this to a more pleasing (closed-form) expression. Perhaps more time studying Wilf's <a href="http://www.math.upenn.edu/~wilf/DownldGF.html" rel="nofollow"><em>generatingfunctionology</em></a> will yield better results.</p> <p>The asker also mentions the special case where the $k \leq p$ constraint is ignored (which is equivalent to the situation when $p_i \geq s$ for all $i$). In this case, we can get a better formula. Let $C(n,s)$ denote the desired quantity.</p> <p>First, we recall the definition of the <a href="http://en.wikipedia.org/wiki/Composition_%28number_theory%29" rel="nofollow">composition</a> of an integer. Next, we observe that there are ${s-1}\choose{i-1}$ compositions of $s$ into $i$ (non-zero) parts and that there are ${n}\choose{i}$ ways to distribute these $i$ parts into the $n$ indices (we let the other $n-i$ indices be zero). Thus, we have $$C(n,s) = \Sigma_{i=1}^{min(n,s)} {{s-1}\choose{i-1}} {{n}\choose{i}}$$</p> http://mathoverflow.net/questions/49056/is-pattern-recognition-np-complete/49344#49344 Answer by mhum for Is pattern recognition NP-complete? mhum 2010-12-14T03:05:12Z 2010-12-14T19:22:07Z <p>The key phrase you are looking for is "<strong>resource-bounded Kolmogorov complexity</strong>". <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.9495" rel="nofollow">This paper</a> by Allender, et. al. may be a good starting point. Also, <a href="http://www.research.rutgers.edu/~troyjlee/thesis.html" rel="nofollow">this PhD thesis</a> might provide some helpful background.</p> <p><em>Edited to add</em>:</p> <p>According to the first article, <a href="http://portal.acm.org/citation.cfm?id=92591" rel="nofollow">Ko, K.-I. "On the complexity of learning minimum time-bounded Turing machines", <em>SIAM Journal on Computing</em>, 20 (1991)</a> may be even more relevant. In that paper, Ko demonstrates that determining whether or not computing time-bounded Kolmogorov complexity is NP-hard requires non-relativizing techniques.</p> http://mathoverflow.net/questions/45875/how-can-you-compute-the-number-of-topological-sorts-in-a-dag/45877#45877 Answer by mhum for How can you compute the number of topological sorts in a DAG? mhum 2010-11-12T23:36:48Z 2010-11-12T23:36:48Z <p>This problem is <a href="http://en.wikipedia.org/wiki/Sharp-P-complete" rel="nofollow">#P-complete</a>. See <a href="http://www.math.dartmouth.edu/~pw/papers/sharpstoc.ps" rel="nofollow">"Counting linear extensions is #P-complete"</a>, G. Brightwell and P. Winkler, Proc. 23rd ACM Symposium on the Theory of Computing, 1991</p> http://mathoverflow.net/questions/44015/how-do-i-approach-optimal-control/44030#44030 Answer by mhum for How do I approach Optimal Control? mhum 2010-10-28T22:51:53Z 2010-10-28T22:51:53Z <p>One potential tactic would be start with Estimation Theory rather than Control Theory. I've enjoyed the approach taken in H. Vincent Poor's <a href="http://www.amazon.com/Introduction-Detection-Estimation-Electrical-Engineering/dp/0387941738/" rel="nofollow"><i>An Introduction to Signal Detection and Estimation</i></a>.</p> http://mathoverflow.net/questions/41935/how-to-solve-a-generalization-of-the-coupon-collectors-problem/41945#41945 Answer by mhum for How to solve a generalization of the Coupon Collector's problem mhum 2010-10-12T21:40:48Z 2010-10-12T21:40:48Z <p>Perhaps this is naive, but shouldn't the expected number of trials be $M/m * T$ where $T$ is the expected number of trials when $M = m$ (i.e.: in the case worked out by Newmann &amp; Shepp)? If half the coupons are useless to you, wouldn't it just take twice as long to collect the ones you wanted?</p> http://mathoverflow.net/questions/41059/generating-unique-combinations-from-a-list-of-possible-repeated-characters/41301#41301 Answer by mhum for Generating Unique Combinations from a list of possible repeated characters mhum 2010-10-06T17:35:48Z 2010-10-06T17:35:48Z <p>Suppose that your list contains $k$ distinct characters and the $i^{th}$ character appears $n_i$ times, for $1 \leq i \leq k$. Then, each combination corresponds to a vector of integers $(x_1, x_2, \ldots, x_k)$ where $0 \leq x_i \leq n_i$.</p> http://mathoverflow.net/questions/129812/hardness-of-approximation-of-dominating-set Comment by mhum mhum 2013-05-07T15:19:33Z 2013-05-07T15:19:33Z I stand corrected. The approximation ratios for Set Cover do appear to be independent of the number of sets. I'm not sure why I thought otherwise. http://mathoverflow.net/questions/129812/hardness-of-approximation-of-dominating-set Comment by mhum mhum 2013-05-06T23:11:18Z 2013-05-06T23:11:18Z If I understand your objection correctly, I think this issue may be resolved by observing that the problem size of Set Cover is related to the size of the universe set <i>and</i> all the subsets. The subsets constitute part of the input for Set Cover. http://mathoverflow.net/questions/87061/a-pairing-problem-mb-related-to-wick-theorem Comment by mhum mhum 2012-01-31T21:14:32Z 2012-01-31T21:14:32Z @spanferkel: Ah. Understood. I misread. http://mathoverflow.net/questions/87061/a-pairing-problem-mb-related-to-wick-theorem Comment by mhum mhum 2012-01-31T19:39:58Z 2012-01-31T19:39:58Z @spanferkel: is the complement of $2nK_3$ the same as the complete tri-partitite graph $K_{2n, 2n, 2n}$? http://mathoverflow.net/questions/79717/does-a-notion-of-convex-graph-make-sense Comment by mhum mhum 2011-11-01T23:03:20Z 2011-11-01T23:03:20Z @Valerio Caprano: In property one, do you require that $[x,y]$ is non-empty for all $x,y$? If not, you could take $\Gamma = E$ for any $X = (V,E)$ which will satisfy properties one through three. I don't have a sense of what contractibility might mean in the case of graphs. http://mathoverflow.net/questions/79717/does-a-notion-of-convex-graph-make-sense Comment by mhum mhum 2011-11-01T21:52:20Z 2011-11-01T21:52:20Z I am mistaken. It turns out not to be the case that $\Gamma$ forms a tree. Consider $X$ to be a triangle with $\Gamma$ equal to the three edges. http://mathoverflow.net/questions/79717/does-a-notion-of-convex-graph-make-sense Comment by mhum mhum 2011-11-01T18:40:52Z 2011-11-01T18:40:52Z Ah, okay. In that case, would that imply that the union of all paths in $\Gamma$ forms a tree inside of $X$? Maybe I am still confused? http://mathoverflow.net/questions/79717/does-a-notion-of-convex-graph-make-sense Comment by mhum mhum 2011-11-01T17:50:14Z 2011-11-01T17:50:14Z I may have misunderstood your definition, but it seems to me that the first property implies that there is a unique path between any two vertices. If that is the case, then X is a tree, extremal vertices appear to be leaves in the tree, and the second property seems to imply that the graph is just a path. http://mathoverflow.net/questions/78712/repeated-function-resulting-in-quadratic-time Comment by mhum mhum 2011-10-21T01:28:16Z 2011-10-21T01:28:16Z Maybe the asker is thinking of the specific case where $r(f,2^n) = n^2$? http://mathoverflow.net/questions/78635/p-vs-np-and-owfs/78643#78643 Comment by mhum mhum 2011-10-20T20:54:48Z 2011-10-20T20:54:48Z I guess the unspoken assumption which should be spoken is &quot;given our current knowledge&quot;. That is to say, as far as I know, we do not yet have any additional results that when combined with $P \neq NP$ implies either the existence or non-existence of one-way functions. Results in this line of investigation would likely be very interesting. http://mathoverflow.net/questions/78635/p-vs-np-and-owfs/78643#78643 Comment by mhum mhum 2011-10-20T20:05:22Z 2011-10-20T20:05:22Z Perhaps it is more accurate to say that $P\neq NP$ alone does not imply the existence of one-way functions? Or, that $P\neq NP$ is consistent with the existence of one-way functions and also consistent with the non-existence of one-way functions? My understanding is that the exact manner in which $P\neq NP$ determines the existence of one-way functions. Roughly, if NP problems are hard only in the worst-case but easy on average (for appropriate definitions of hard, easy, and average), OWF don't exist; if NP problems are hard on average, OWF may (but are not guaranteed to) exist. http://mathoverflow.net/questions/71994/what-is-the-number-of-maximal-antichain-in-a-poset/72033#72033 Comment by mhum mhum 2011-08-06T00:32:46Z 2011-08-06T00:32:46Z Counting antichains in a partial order is #P-complete according to the abstract for &quot;The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected&quot;, SIAM J. Comput. 12 (1983), 777-788 (<a href="http://epubs.siam.org/sicomp/resource/1/smjcat/v12/i4/p777_s1?isAuthorized=no" rel="nofollow">epubs.siam.org/sicomp/resource/1/smjcat/v12/i4/&hellip;</a>). http://mathoverflow.net/questions/71022/entangled-permutations-of-a-multiset Comment by mhum mhum 2011-07-26T06:49:38Z 2011-07-26T06:49:38Z Does anything nice happen to the horrible-looking formula if $a_1 = a_2 = \ldots = a_m$? http://mathoverflow.net/questions/69873/what-is-the-complexity-of-this-problem/70070#70070 Comment by mhum mhum 2011-07-13T08:11:26Z 2011-07-13T08:11:26Z You can also find a proof that MHW is NP-complete in &quot;On the Inherent Intractability of Certain Coding Problems&quot; (1978) by Berlekamp, et al. <a href="http://authors.library.caltech.edu/5607/1/BERieeetit78.pdf" rel="nofollow">authors.library.caltech.edu/5607/1/&hellip;</a> http://mathoverflow.net/questions/68570/existence-of-a-set-of-valid-busy-beaver-entries Comment by mhum mhum 2011-06-23T04:16:44Z 2011-06-23T04:16:44Z @sarannmr: If you do not accept the existence of the non-computable, then you must also reject the existence of uncountable things. Without the uncountable, you do not have the real numbers, only the rationals. This rejection is apparently also a feature of intuitionism (<a href="http://en.wikipedia.org/wiki/Intuitionism" rel="nofollow">en.wikipedia.org/wiki/Intuitionism</a>). Maybe worth a look?