User mohammad al-turkistany - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T02:27:59Z http://mathoverflow.net/feeds/user/8784 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/128233/how-dense-is-the-set-of-asymmetric-graphs How dense is the set of asymmetric graphs? Mohammad Al-Turkistany 2013-04-21T10:40:25Z 2013-04-22T04:12:01Z <p>On $n$ nodes, we have $2^{n(n-1)/2}$ graphs. Asymmetric graph is a graph that has only trivial automorphism. We known that asymptotically almost all finite graphs are asymmetric. Therefore, in the limit, the ratio of asymmetric graphs approaches 1. </p> <p>However, I did not find any reference that provides lower bound on the number of asymmetric graphs on $n$ nodes. What is known about the density of asymmetric graphs as a function of the number of nodes $n$?</p> http://mathoverflow.net/questions/109126/redundancy-and-structure-of-computational-problems Redundancy and Structure of computational problems Mohammad Al-Turkistany 2012-10-08T09:22:40Z 2013-01-24T16:22:00Z <p>It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). I'm interested in the different formal notions for structure of computational problems and redundancy measures.</p> <p>What are the major results known about such formal notions for computational problems? A recent survey of such notions would be very nice.</p> <p>It was posted on <a href="http://cstheory.stackexchange.com/questions/12759/redundancy-and-structure-of-computational-problems" rel="nofollow">TCS stackexchange</a> without any answer.</p> http://mathoverflow.net/questions/91483/best-lower-bound-for-proof-complexity-of-graph-asymmetry Best lower bound for proof complexity of graph asymmetry Mohammad Al-Turkistany 2012-03-17T18:26:30Z 2012-07-01T12:06:22Z <p><a href="http://en.wikipedia.org/wiki/Graph_automorphism_problem" rel="nofollow">Graph automorphism problem</a> ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in $NP$-intermediate. I'm looking for references that study the certificate complexity of graph non-automorphism (GNA= {G| G is rigid or asymmetric graph}). </p> <p>What is the best known lower bound on the length of certificates that prove a graph is rigid ($G \in GNA$)? Also, Is there a plausible conjecture that prohibits sub-exponential certificates for $CoNP$-complete problems (analogues to ETH)?</p> http://mathoverflow.net/questions/90123/np-hardness-of-a-graph-partition-problem NP-hardness of a graph partition problem? Mohammad Al-Turkistany 2012-03-03T16:00:05Z 2012-03-05T18:29:56Z <p>I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic? Here $E$ is partitioned into two disjoint sets $E_1$ and $E_2$. Sets $V_1$ and $V_2$ are not necessarily disjoint. $E1∪E2=E$ and $V1∪V2=V$.</p> <p>This problem is at least as hard as Graph Isomorphism Problem. I guess it is harder than Graph Isomorphism but not NP-hard.</p> <blockquote> <p>Is this partition problem $NP$-hard?</p> </blockquote> <p>I posted it on <a href="http://cstheory.stackexchange.com/questions/10477/np-hardness-of-a-graph-partition-problem" rel="nofollow">CS theory</a> without any answer.</p> http://mathoverflow.net/questions/64942/partition-a-square-into-sub-rectangles-with-restrictions Partition a square into sub-rectangles with restrictions Mohammad Al-Turkistany 2011-05-13T21:55:29Z 2011-12-18T04:39:16Z <p>Is there an algorithm to generate all partitions of given square by using $n$ vertical and $n$ horizontal lines into sub-rectangles under the following restrictions:</p> <p>1- No vertical line crosses any horizontal line and vice versa.</p> <p>2- Each vertical line touches exactly three horizontal lines and each horizontal line touches exactly three vertical lines.</p> <p>Here is an example when $n=4$</p> <p><img src="http://i.imgur.com/FbGDD.jpg" alt="enter image description here"></p> http://mathoverflow.net/questions/68622/np-complete-variants-of-npi-problems NP-complete variants of NPI problems Mohammad Al-Turkistany 2011-06-23T15:41:29Z 2011-06-27T10:59:57Z <p>Motivated by these posts, <a href="http://cstheory.stackexchange.com/q/4769/495" rel="nofollow">An NP-complete variant of factoring</a> and <a href="http://cstheory.stackexchange.com/q/871/495" rel="nofollow">Relationship between symmetry and computational intractability</a>, It seems to be worthwhile to investigate the different factors that increase the hardness of problems in NPI. I'm interested in other NP-complete variants of problems of intermediate complexity. </p> <p>Is there a recent survey paper of $NP$-complete variants of problems of intermediate complexity (problems between P and NP-complete)?</p> <p>Cross posted on <a href="http://cstheory.stackexchange.com/questions/6761/np-complete-variants-of-npi-problems" rel="nofollow">TCS StackExchange</a> </p> <p>UPDATE: Bounty may be awarded to an answer that gives other interesting NPI problems that have an $NP$-complete variant.</p> http://mathoverflow.net/questions/62849/complexity-of-a-problem-related-to-3d-matching Complexity of a problem related to 3D matching? Mohammad Al-Turkistany 2011-04-24T16:07:26Z 2011-04-24T16:07:26Z <p>Given a set of triples of a base set $S$, find a subset of triples such that each element in $S$ appears exactly in one triple. This problem is NP-complete by reduction from NP-complete problem 3D Matching.</p> <p>I'm interested in the complexity of related problem. What is the complexity of finding a subset of triples such that each element in $S$ appears exactly in two triples?</p> <p>Has this problem been studied in the literature? I'd greatly appreciate pointing me to references.</p> http://mathoverflow.net/questions/52583/complexity-of-max-bisection-on-cubic-planar-graphs Complexity of Max Bisection on cubic planar graphs? Mohammad Al-Turkistany 2011-01-20T05:30:33Z 2011-04-15T14:22:14Z <p>Max Bisection problem is to partition the set of nodes into two equal size sets such that the number of crossing edges is maximized. Max Bisection is $NP$-complete on cubic graphs and also on planar graphs.</p> <blockquote> <p>What is the complexity of Max Bisection on cubic planar graphs? Is it $NP$-complete?</p> </blockquote> <p>Cross posted on <a href="http://cstheory.stackexchange.com/questions/4323/complexity-of-max-bisection-on-cubic-planar-graphs" rel="nofollow">SE tcs</a> <a href="http://cstheory.stackexchange.com/questions/4323/complexity-of-max-bisection-on-cubic-planar-graphs" rel="nofollow"></a></p> http://mathoverflow.net/questions/61531/complexity-of-finding-disjoint-2-factors-with-equal-cardinality-in-cubic-graphs Complexity of finding disjoint 2-factors with equal cardinality in cubic graphs? Mohammad Al-Turkistany 2011-04-13T10:41:01Z 2011-04-13T10:41:01Z <p>Finding a connected 2-factor that contains every node in cubic graphs is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding vertex disjoint 2-factors with equal cardinality in cubic graphs.</p> <p>I suspect that it is $NP$-complete but I'm not able to find a reference. Also, What is the complexity of finding vertex disjoint 2-factors with equal cardinality in planar cubic bipartite graphs? Is it $NP$-complete?</p> <p>Providing references is highly appreciated. </p> http://mathoverflow.net/questions/52590/abstract-notion-for-energy-complexity-of-computational-problems Abstract notion for energy complexity of computational problems? Mohammad Al-Turkistany 2011-01-20T07:31:53Z 2011-03-03T03:50:04Z <p>Energy is very valuable computational resource especially in mobile computing. Optimizing the energy consumed during the execution of algorithms has significant practical implications. Intuitively, It seems that such abstract energy measure has to be correlated to the time complexity, the space complexity, and the frequency of space (memory) access operations. Communications costs should be accounted for if we consider distributed computing model.</p> <blockquote> <p>Are there abstract notions of energy (possibly analogous to the action quantity in physics) which could be useful for establishing energy-complexity classes for computational problems?</p> </blockquote> <p>This is a follow-up to this question on <a href="http://cstheory.stackexchange.com/questions/4204/formal-notion-for-energy-complexity-of-computational-problems" rel="nofollow">SE TCS</a> <a href="http://cstheory.stackexchange.com/questions/4204/formal-notion-for-energy-complexity-of-computational-problems" rel="nofollow"></a></p> http://mathoverflow.net/questions/56310/complexity-of-edge-coloring-in-planar-graphs Complexity of edge coloring in planar graphs? Mohammad Al-Turkistany 2011-02-22T19:21:37Z 2011-02-22T19:46:15Z <p>I asked this on StackExchange TCS but did not get a satisfactory answer:</p> <p>Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". However, 3-edge coloring of cubic graphs is $NP$-complete. I'm wondering if the problem is still hard for cubic planar graphs.</p> <blockquote> <p>What is the complexity of 3-edge coloring for cubic planar graphs?</p> </blockquote> <p>Also, It is conjectured that $\Delta$-edge coloring is $NP$-hard for planar graphs with maximum degree $\Delta \in${4,5}.</p> <blockquote> <p>Has any progress been made towards resolving this conjecture?</p> </blockquote> <p>Marek Chrobak and Takao Nishizeki. Improved edge-coloring algorithms for planar graphs. Journal of Algorithms, 11:102-116, 1990</p> http://mathoverflow.net/questions/46051/hardness-of-discrete-geometric-area-minimization-problem Hardness of discrete geometric area minimization problem? Mohammad Al-Turkistany 2010-11-14T15:43:25Z 2010-11-16T00:25:04Z <p>This question was originally posted on: <a href="http://cstheory.stackexchange.com/questions/2844/hardness-of-geometric-area-minimization-problem" rel="nofollow">cstheory.stackexchange</a> <a href="http://cstheory.stackexchange.com/questions/2844/hardness-of-geometric-area-minimization-problem" rel="nofollow"></a></p> <p>Given $xyz=C$ where $x, y,$ and $z$ are integer variables and $C$ is integer constant. Assume all integers are encoded in binary.</p> <blockquote> <p>What is the complexity of finding $x, y, z$ such that $xy+xz+yz$ has minimum value? Is there any subexponential algorithm that solves this problem? Does the problem become easier when integers are encoded in unary?</p> </blockquote> <p><strong>Motivation</strong>: I'm interested in the following generalized problem:</p> <p><strong>Input</strong>: integers $C$ and $K$</p> <p><strong>Problem</strong>: Find integers $x$, $y$, and $z$ such that $xyz\ge C$ and $xy+xz+yz\le K$</p> http://mathoverflow.net/questions/44673/human-checkable-proof-of-the-four-color-theorem Human checkable proof of the Four Color Theorem? Mohammad Al-Turkistany 2010-11-03T13:20:15Z 2010-11-03T14:25:45Z <p>Four Color Theorem is equivalent to the statement: "Every cubic planar bridgeless graphs is 3-edge colorable". There is computer assisted proof given by Appel and Haken. Dick Lipton in of his <a href="http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/" rel="nofollow">beautiful blogs</a> <a href="http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/" rel="nofollow"></a> posed the following open problem:</p> <blockquote> <p>Are there non-computer based proofs of the Four Color Theorem?</p> </blockquote> <p>Surprisingly, While I was reading this paper, Anshelevich and Karagiozova, <a href="http://portal.acm.org/citation.cfm?id=1250790.1250849" rel="nofollow">Terminal backup, 3D matching, and covering cubic graphs</a> <a href="http://portal.acm.org/citation.cfm?id=1250790.1250849" rel="nofollow"></a>, the authors state that Cahit proved that "every 2-connected cubic planar graph is edge-3-colorable" which is equivalent to the Four Color Theorem (I. Cahit, Spiral Chains: The Proofs of Tait's and Tutte's Three-Edge-Coloring Conjectures. arXiv preprint, math CO/0507127 v1, July 6, 2005).</p> <blockquote> <p>Does Cahit's proof resolve the open problem in Lipton's blog by providing non-computer based proof for the Four Color Theorem?</p> </blockquote> <p>Cross posted on cstheory.stackexchange.com as <a href="http://cstheory.stackexchange.com/questions/2597/human-checkable-proof-of-the-four-color-theorem-closed" rel="nofollow">Human checkable proof of the Four Color Theorem?</a> <a href="http://cstheory.stackexchange.com/questions/2597/human-checkable-proof-of-the-four-color-theorem-closed" rel="nofollow"></a> </p> http://mathoverflow.net/questions/40169/complexity-of-a-variant-of-the-mandelbrot-set-decision-problem Complexity of a variant of the Mandelbrot set decision problem? Mohammad Al-Turkistany 2010-09-27T15:54:12Z 2010-09-30T13:42:35Z <p>This is a modified version of a question posted on <a href="http://cstheory.stackexchange.com/questions/778" rel="nofollow">StackExchange TCS.</a> <a href="http://cstheory.stackexchange.com/questions/778" rel="nofollow"></a></p> <p>Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number. Let us define</p> <p>$M=${$(c,k,r) |$ In the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ of first $k$ complex numbers, there is a subset $T$ of complex numbers such that the sum of the real parts $\gt$ $r.k$ and the sum of imaginary parts $\gt$ $r.k$}</p> <p>where $r$ is real number and $k$ is an integer in unary.</p> <p>Here is a geometric interpretation, since each $P_c^i(0)$ is a vector in 2D, we want to find the maximum size square obtainable by the summation of a subset of two dimensional vectors.</p> <blockquote> <p>Is there an efficient algorithm in the real computing model (i.e the Blum-Shub-Smale model) for deciding set $M$ or is it $NP$-complete ?</p> </blockquote> <p><strong>EDIT:</strong> Is there any NP-complete problem related to Mandelbrot set?</p> http://mathoverflow.net/questions/38990/self-improvement-property-of-optimazation-problems Self-improvement property of optimazation problems? Mohammad Al-Turkistany 2010-09-16T16:33:08Z 2010-09-16T17:42:17Z <p>Maximum CLIQUE problem is very hard to approximate. It has a self-improvement property defined using graph product which is utilized to prove hardness of approximation results. One such example is ruling out any constant factor polynomial time approximation scheme unless $P = NP$. Furthermore, using booster products, we can show that its NP-hard to approximate Max CLIQUE within a factor of $n^{\epsilon}$ for some value $\epsilon >0$. Also, Maximum independent set problem has a self-improvement property which is used to rule out constant factor approximation (assuming $P \ne NP$).</p> <p>I would like to gain insights into the failure of many optimization problems to have self-improvement property. What are the common features of hard to approximate problems that poses self-improvement property? </p> <blockquote> <p>Under what conditions an optimization problem can not poses self-improvement property? </p> </blockquote> http://mathoverflow.net/questions/90123/np-hardness-of-a-graph-partition-problem Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2012-03-04T14:27:50Z 2012-03-04T14:27:50Z Thanks Hebert. GT12 is different since the required isomorphism is fixed by graph $H$. http://mathoverflow.net/questions/64942/partition-a-square-into-sub-rectangles-with-restrictions/64947#64947 Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2011-05-14T22:17:51Z 2011-05-14T22:17:51Z Here is the paper: de Fraysseix, de Mendez, and Pach: Representation of planar graphs by segments, in: Intuitive Geometry. http://mathoverflow.net/questions/64942/partition-a-square-into-sub-rectangles-with-restrictions/64947#64947 Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2011-05-14T18:06:57Z 2011-05-14T18:06:57Z Thanks Mark. There is a theorem which states that every planar bipartite graph is representable by a contact graph of horizontal and vertical line segments. I'm looking for explicit algorithm to construct contact graphs that correspond to cubic planar bipartite graphs. http://mathoverflow.net/questions/62849/complexity-of-a-problem-related-to-3d-matching Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2011-04-24T18:25:24Z 2011-04-24T18:25:24Z Which reduction do you have in mind for NP-hardness? http://mathoverflow.net/questions/61531/complexity-of-finding-disjoint-2-factors-with-equal-cardinality-in-cubic-graphs Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2011-04-13T10:49:34Z 2011-04-13T10:49:34Z $NP$-completeness refers to the decision version of the problem. http://mathoverflow.net/questions/59775/undecidability-church-turing-thesis-and-p-poly Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2011-04-03T05:57:14Z 2011-04-03T05:57:14Z @Phil, Nice answer. You should convert your comment to an answer. http://mathoverflow.net/questions/46051/hardness-of-discrete-geometric-area-minimization-problem/46101#46101 Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2010-11-16T12:23:05Z 2010-11-16T12:23:05Z Thanks Aaron, Does your answer suggest that exhaustive search ($2^{\Omega (n)}$−time) is unavoidable? http://mathoverflow.net/questions/46051/hardness-of-discrete-geometric-area-minimization-problem Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2010-11-14T20:38:16Z 2010-11-14T20:38:16Z Indeed, x,y,z are positive integers. http://mathoverflow.net/questions/46051/hardness-of-discrete-geometric-area-minimization-problem Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2010-11-14T20:37:07Z 2010-11-14T20:37:07Z @Qiaochu, Is exhaustive search avoidable in either case? Are you aware of any subexponential-time algorithms? http://mathoverflow.net/questions/46051/hardness-of-discrete-geometric-area-minimization-problem Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2010-11-14T16:18:21Z 2010-11-14T16:18:21Z It think the first problem is a special case of the second problem. Am I right? http://mathoverflow.net/questions/38990/self-improvement-property-of-optimazation-problems Comment by Mohammad Al-Turkistany Mohammad Al-Turkistany 2010-09-17T18:08:18Z 2010-09-17T18:08:18Z I agree, there is no rigorous systematic study of Self-improvement properties of optimization problems. All examples I have seen are Ad-hoc in nature. For instance, Karger used it to prove that the Longest Path cannot be approximated within $O(\log n)$ unless P=NP. Karger, Motwani, Ramkumar, [On approximating the longest path in a graph](<a href="http://www.springerlink.com/content/861m67dd2euu4qlj/" rel="nofollow">springerlink.com/content/861m67dd2euu4qlj</a>) &lt;a href=&quot;<a href="http://www.springerlink.com/content/861m67dd2euu4qlj/&quot;&gt;foo&lt;/a&gt" rel="nofollow">springerlink.com/content/861m67dd2euu4qlj/&hellip;</a>;