Archive for the ‘US PATENT APPLICATION RESEARCH’ Category

Algorítmica y complejidad computacional. i.o. SUBEXP.

marzo 29, 2017

Disclaimer. El problema para publicar entradas en el blog se resolvió finalmente mucho más rápido de lo que esperaba y sin necesidad de ayuda externa. Los foros fueron suficientes.

Tras publicar en forma de comentarios, volvemos a la forma  de publicación habitual. En este nuevo periodo del blog nos vamos a centrar sobre todo en el mismo tipo de publicaciones que en la primera fase (dos primeros años) del blog. No obstante paramayor organización, vamos a seguir actualizando en los comentarios.  Fin de disclaimer.

Antes de volver a mancharnos las manos con el lápiz y la goma para rematar los flecos que quedan dentro de nuestra investigación (esto es necesario para la siguiente y última fase del proyecto y espero resolverlos pronto o no resolverlos y pasar a siguiente fase de cualquier manera), calentamos motores poniéndonos al día en complejidad computacional (por una parte me sigue costando leer sobre estos temas, por otra parte en esta última ronda estoy llegando más lejos en la comprensión de algunos temas; así es la madurez).

Conozco hoy por primera vez una clase, i.o. SUBEXP (infinitely often SUBEXP) aparentemente

(more…)

HPC. Generalizing 2-generated Cayley Digraphs (2): its relation with Plesnik digraphs.

marzo 22, 2017

Disclaimer. Esta entrada parte de una parte de la entrada anterior (publicada ayer) que hemos redactado de nuevo. Es una entrada en parte de investigación (la parte de actualizaciones) y puede contener errores. 

El otro día me acordé del resultado de Plesnik y ayer lo he estado releyendo. Primero me acordé al hilo de un comentario que hicimos en la entrada sobre IBM Q sobre reducciones, pues explica muy claramente las reducciones de SAT-CNF a un tipo de dígrafos que para nosotros es muy interesante.

(more…)

Algorítmica y complejidad computacional. Recopilación de enlaces marzo 2017.

marzo 21, 2017
  1. Desde hoy mismo he empezado a ver de nuevo a diario algunas categorías de Arxiv. A continuación algunos artículos que he visto. También otros artículos no necesariamente de Arxiv. Ordenados por orden de interés.
  2. Cayley graphs on groups with commutator subgroup of order 2p are hamiltonian. Dave Witte Morris Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, Alberta, T1K 3M4, Canada Abstract. We show that if G is a finite group whose commutator subgroup [G,G] has order 2p, where p is an odd prime, then every connected Cayley graph on G has a hamiltonian cycle. Leyendolo, aunque se refiere a Grafos de Cayley, que nos interesan menos. En la introducción se resume muy claramente el resultado: Let G be a finite group. It is easy to show that if G is abelian (and |G| > 2), then every connected Cayley graph on G has a hamiltonian cycle. (See Definition 2.1 for the definition of the term Cayley graph.) To generalize this observation, one can try to prove the same conclusion for groups that are close to being abelian. Since a group is abelian precisely when its commutator subgroup is trivial, it is therefore natural to try to find a hamiltonian cycle when the commutator subgroup of G is close to being trivial. The following theorem, which was proved in a series of papers, is a well-known result along these lines. Theorem 1.1 (Marusiˇ c [ ˇ 13], Durnberger [4, 5], 1983–1985). If the commutator subgroup [G,G] of G has prime order, then every connected Cayley graph on G has a hamiltonian cycle. D. Marusiˇ c (personal communication) suggested more than thirty years ago that it ˇ should be possible to replace the prime with a product pq of two distinct primes: Research Problem 1.2 (D. Marusiˇ c, personal communication, 1985) ˇ . Show that if the commutator subgroup of G has order pq, where p and q are two distinct primes, then every connected Cayley graph on G has a hamiltonian cycle. This has recently been accomplished when G is either nilpotent [8] or of odd order [14]. As another step toward the solution of this problem, we establish the special case where q = 2: Theorem 1.3. If the commutator subgroup of G has order 2p, where p is an odd prime, then every connected Cayley graph on G has a hamiltonian cycle. See the bibliography of [12] for references to other results on hamiltonian cycles in Cayley graphs. Relacionado: la página de wkipedia sobre commutator subgroup. Extracto: The commutator subgroup of the symmetric group Sn is the alternating group An. Obviamente An no entrará, ni en general ni en particular, dentro del resultado de este artículo.
  3. A CONJECTURE ON DETERMINING WHICH (n, k)-STAR GRAPHS ARE NOT CAYLEY GRAPHS KARIMAH SWEET, LI LI, EDDIE CHENG, LASZL ´ O LIPT ´ AK, AND DANIEL STEFFY ´ Abstract. In this paper, we continue the work begun by Cheng et al. on classifying which of the (n, k)-star graphs are Cayley. We present a conjecture for the complete classification, and prove an asymptotic version of the conjecture, that is, the conjecture is true for all k ≥ 2 when n is sufficiently large. For k = 2, . . . , 15 we prove that the conjecture is true for all n ≥ k + 2 (with the possible exception of S17,14). The proof reveals some unexpected connection between (n, k)-star graphs and the classification of multiply transitive groups (which is closely related to the classification of finite simple groups).
  4. Graph Theory and Interconnection NetworksEscrito por Lih-Hsing Hsu,Cheng-Kuan Lin. He visto este libro en la bibliografía. Para mi sorpresa gran parte del contenido de este libro de 2009 trata de recorridos hamiltonianos. Pese a la sorpresa, seguramente ya lo hemos enlazado en alguna que otra ocasión.

  5. Nonexistence of Efficient Dominating Sets in the Cayley Graphs Generated by Transposition Trees of Diameter 3 Italo J. Dejter University of Puerto Rico Rio Piedras, PR 00936-8377 e-mail: italo.dejter@gmail.com Abstract Let Xd n be a Cayley graph generated by a transposition tree of diameter d. It is known that every V (Xd n) = Sn with d < 3 splits into efficient dominating sets. However, no X3 n has efficient dominating sets, shown in this work along related developments.
  6. Una familia de grafos que  no conocía: los I-Graphs. Un poco de historia: In 1950 a class of generalized Petersen graphs was introduced by Coxeter and around 1970 popularized by Frucht, Graver and Watkins. The family of I-graphs mentioned in 1988 by Bouwer et al. represents a slight further albeit important generalization of the renowned Petersen graph….I-graphs were introduced in the Foster census [5] and form a natural generalization of the generalized Petersen graphs introduced by Coxeter [8] and named by Watkins [26] .  Relacionado. 

    Lovrečič Saražin, M. “A Note on the Generalized Petersen Graphs That Are Also Cayley Graphs.” J. Combin. Th. B 69, 226-229, 1997.

    Nedela, R. and Škoviera, M. “Which Generalized Petersen Graphs Are Cayley Graphs?” J. Graph Th. 19, 1-11, 1995.

  7. Symmetric powers of permutation representations of finite groups and primitive colorings on polyhedrons Tomoyuki Tamura Graduate school of Mathematics Kyushu University 2017 Abstract In this paper1 , we define a set which has a finite group action and is generated by a finite color set, a set which has a finite group action, and a subset of the set of non negative integers. we state its properties to apply one of solution of the following two problems, respectively. First, we calculate the generating function of the character of symmetric powers of permutation representation associated with a set which has a finite group action. Second, we calculate the number of primitive colorings on some objects of polyhedrons. It is a generalization of the calculation of the number of primitive necklaces by N.Metropolis and G-C.Rota.. Probablemente sin interés para nuestro  tema. 
  8. The Unconstrained Binary Quadratic Programming Problem: A Survey. Este es el problema para el que está optimizada la máquina de D-wave. UBQP = QUBO es el problema al que se deben de reducir los problemas tratables por D-Wave. En el artículo siguiente relacionado comentan que esta reducción (una instancia de subgraph isomorphism) podría ser un “cuello de botella”, en el sentido en el que comentábamos en la anterior entrada. Por mucho que tu máquina funcione instántaneamente, si para construir el input con el que va a trabajar tienes que resolver un problema exponencial en el peor caso, mal vas. Matar moscas a cañonazos. Luego matizan y es posible que  los  input para la máquina de D-Wave eviten este problema. También es posible que sean entonces inputs sencillos en cualquier caso, que admitan resolución por algoritmo polinómico clásico. Según leí en los blogs a los que enlacé ayer, por ahí van los tiros. In order to solve a problem, D-Wave needs it to be first translated into a QUBO.  This QUBO in turns needs to be transformed into an Ising spin glass into their machine.  To cut  along story short, it means that the QUBO problem must be mapped onto a special graph, called a chimera graph

 

  1. Internet of Things: An Overview Farzad Khodadadi, Amir Vahid Dastjerdi, and Rajkumar Buyya Abstract As technology proceeds and the number of smart devices continues to grow substantially, need for ubiquitous context-aware platforms that support interconnected, heterogeneous, and distributed network of devices has given rise to what is referred today as Internet-ofThings. However, paving the path for achieving aforementioned objectives and making the IoT paradigm more tangible requires integration and convergence of different knowledge and research domains, covering aspects from identification and communication to resource discovery and service integration. Through this chapter, we aim to highlight researches in topics including proposed architectures, security and privacy, network communication means and protocols, and eventually conclude by providing future directions and open challenges facing the IoT development. He visto este artículo en la categoría de paralelismo. Me ha sorprendido verlo ahí (también muchos otros). A ver si me entero que sobre que va este tema. Prioridad cero. Relacionado. 1. J. Bradley, J. Barbier, and D. Handler, “Embracing the internet of everything to capture your share of $14.4 trillion,” 2014. [Online]. Available: http://www.cisco.com/c/dam/en us/about/ac79/docs/innov/IoE Economy.pdf 2. J. Manyika, M. Chui, P. Bisson, J. Woetzel, R. Dobbs, J. Bughin, and D. Aharon. (2015, June) Unlocking the potential of the internet of things. McKinsey Global Institute. [Online]. 22 Shuo Chen et al. Available: http://www.mckinsey.com/business-functions/business-technology/ our-insights/the-internet-of-things-the-value-of-digitizing-the-physical-world 3. (2014, Jan) Cisco delivers vision of fog computing to accelerate value from billions of connected devices. Cisco. Press release. [Online]. Available: http://newsroom.cisco.com/release/1334100/Cisco-Delivers-Vision-ofFog-Computing-to-Accelerate-Value-from-Billionsof-Connected-Devices-utmmedium-rss

(more…)

Algorítmica y complejidad computacional. HAMILTON CYCLE PROBLEM THROUGH GRASSMANN NUMBERS.

marzo 14, 2017

Hago una entrada específica sobre un apartado de un artículo que he visto hoy en arxiv, que  parece interesante pero sobre el que, tras una primera lectura en diagonal, no he entendido nada. Pero nada nada, lo cual me preocupa :-(.

Como me tengo que poner las pilas sobre estos temas  de nuevo, temas que tengo completamente oxidados, es una buena ocasión para comenzar…Lo siento lector, pero voy a empezar a publicar bastante más sobre estos temas.

Título. P=?NP as minimization of degree 4 polynomial, or Grassmann number problem

AbstractWhile the P vs NP problem is mainly being attacked form the point of view of discrete mathematics, this paper propses two reformulations into the field of abstract algebra and of continuous global optimization – which advanced tools might bring new perspectives and approaches to attack this problem. The first one is equivalence of satisfying the 3-SAT problem with the question of reaching zero of a nonnegative degree 4 multivariate polynomial. This continuous search between boolean 0 and 1 values could be attacked using methods of global optimization, suggesting exponential growth of the number of local minima, what might be also a crucial issue for example for adiabatic quantum computers. The second discussed approach is using anti-commuting Grassmann numbers θ i, making ( A · diag ( θ i)) n nonzero only if A has a Hamilton cycle. Hence, the P 6=NP assumption implies exponential growth of matrix representation of Grassmann numbers.

En principio no es más que otro paper con una reducción de 3-sat a otros problemas compleidad-computacionalmente equivalentes.

La novedad es que estos otros problemas no son de matemática discreta (al menos uno de ellos; no lo tengo claro con respecto al otro).

Además me ha llamado la atención por un par de temas. Lo publico en el blog para que no se me olvide. Aparentemente, y el mismo autor lo reconoce, atacar el problema de recorridos hamiltonianos por esta vía es matar moscas a cañonazos (el problema es exactamente el mismo que resolver el problema en Digrafos de Cayley teniendo que construir todo el digrafo).

Se pone de manifiesto un vez más lo que ya sabe todo el mundo pero no se si  está incluido en las teorías: un algoritmo consta  al menos de tres partes o fases: la fase de representación del input, la fase de búsqueda de solución (que es lo que normalmente se llama algoritmo) y la fase de expresión o representación de la solución (usualmente llamada output, pero que en realidad es la prueba de la solución, que puede adoptar muchas formas diferentes, unas más largas que otras), y la fase de comunicación de la  solución a una tercera parte.

¿ Tiene sentido considerar esta cuarta fase como diferente a la tercera ?. Dos casos: comunicación de la computadora al ser humano una vez ha obtenido el resultado; o lo mismo de ser humano a ser humano. En el fondo la pregunta es si se puede  optmizar, hacer más sucinto un output, la prueba de una solución, una vez que se conoce la solución en una de sus formas. Ejemplo concreto: obtengo un recorrido hamiltoniano; hay alguna manera de procesar esta solución de tal modo que obtenga una prueba más corta que mostrar la secuencia de vértices ?).  Me temo que no estoy expresando la idea claramente y eso significa que no la tengo clara.

La  contabilidad de complejidad computacional debe de tener  en cuenta el  coste en todas las fases, debe de haber un computo global.

Por otra parte le estoy dando vueltas a un tema desde hace tiempo: al igual que existe la idea de equivalencia de problemas computacionales (mediante reducciones), que está relacionada con las fases de representación del input y del  output, ¿ no existirá una manera de demostrar que dos algoritmos, en su fase de búsqueda de solución ?. Si no el  concepto de algoritmo (fase de búsqueda de solución) queda demasiado abierto. Está el concepto de simulación de un proceso por otro, pero no se si esto se ha bajado a la tierra e integrado en la teoría de complejidad  computacional.

Volviendo al artículo, aunque  utiliza los números de Grassman, y estos se utilizan en alguna rama de la física, el artículo no tiene ninguna relación con la física (según estoy viendo).

Relacionado.  Números de Grassman.

(more…)

IP. Solicitar hoy una patente en EEUU: la visión de los inventores.

enero 29, 2017

Varios artículos sobre la travesía del desierto en que se ha convertido el solicitar una patente hoy en EEUU. Posiblemente sean artículos algo sesgados (hacia una visión demasiado crítica) y que intentan aprovechar la coyuntura (nueva presidencia en EEUU con una política de patentes al parecer bastante indefinida de momento) para presionar y que haya un cambio de rumbo. Realmente me gustaría ver algunas estadísticas para emitir un juicio.

El problema ya no es sólo conseguir la concesión de la patente (cosa que en determinados campos como en las patentes de software, se ha convertido en misión imposible; doy fe, pero sin que sirva de precedente no vamos a entrar en detalles sobre mi caso en esta entrada).

Los problemas sobre los que hablan son todos post-conceisón o post-grant.  Es decir, cuando te la han concedido te esperan, según nos informan en los artículos a los que enlazamos, múltiples nuevas dificultades que yo desconocía (no hablo de dificultades en la comercialización / rentabilización, que ya conocía, sino de litigaciones post-concesión por parte de terceras partes; me voy a empezar a informar; de momento, dados los plazos de la tramitación, yo ya llevo más de 8 años, he aplicado la regla según va viniendo vamos viendo) pero que de realizarse pueden dejar completamente fuera de juego a cualquier inventor con unas posibilidades financieras limitadas.

Según nos comentan en los artículos, lo cierto es que el sistema se ha desequilibrado (de manera claramente consciente por parte de los tres poderes de EEUU: ejecutivo, legislativo y judicial) hacía los grandes jugadores, es decir la multinacionales americanas que campan a  sus anchas (y no sólo en este aspecto). Seguramente los tres poderes han tratado de proteger a la gallina de los huevos de oro. Al parecer todo empezó en 2006 y se ha ido intensificando desde entonces tras múltiples y activas campañas de lobbying por parte de estas multinacionales. Ahora, además de atropellar, también les sale prácticamente gratis robar.

¿ Puede haber cambios al respecto con la nueva presidencia a favor de los pequeños inventores ? Esperemos acontecimientos. Hasta que se despejen las incógnitas, para los pequeños inventores domiciliados en EEUU hay esperanzas. Creo recordar que hubo alguna presidencia (ahora no recuerdo cual) que le plantó cara a la gran empresa. Pero este no es mi caso, yo no tengo domicilio en EEUU. Teniendo en cuenta la deriva nacionalista que está tomando la nueva presidencia (es muy pronto para llegar a conclusiones, pero ya se ven señales claras), no espero nada. Por supuesto no pienso que pueda haber una instrucción genérica para mi caso, pero sí podría haber (aunque lo dudo) una instrucción genérica para patentes solicitadas por extranjeros.

En fin sin más preliminares los enlaces indicados:

Una  entrada de un inventor en serie (que ha comercializado varias de sus patentadas invenciones) y que ha decidido abandonar su última solicitud ya que los costes y riesgos son mucho mayores que los posibles beneficios.

Nota.

Yo no voy a abandonar mi segunda solicitud. Pero en mi vida me meteré en otra patente, aunque acabe rentabilizando estas dos primeras, cosa que dudo por lo ya indicado (según voy leyendo, estoy más pesimista que nunca). Y recomiendo activa y encarecidamente a cualquiera que lea estas líneas que dedique su tiempo a cualquier otra actividad que no sea inventar. Dadas las circunstancias, será una pérdida de tiempo sí o sí: la vía de la patente es una vía muerta y las otras (el secreto comercial) en mi opinión también, pues te dejan muy poco margen.

Fin de nota.

–Y dos entradas de otro inventor en serie que también ha rentabilizado anteriores patentadas invenciones. También con un mensaje todo menos incentivador. La primera y la segunda.  Las dos bastante técnicas.

Algorítmica y complejidad computacional. Un nuevo estilo / problema en matemáticas.

enero 26, 2017

Lo hemos comentado muy recientemente en una entrada anterior (perdón por la autocita).

Es el nuevo estilo de publicación: sin estar seguro de que lo que se tiene entre manos y publica es 100% correcto. Al igual que los problemas que se intentan resolver, las demostraciones son cada vez más complejas y necesitan múltiples mentes para la comprobación de su corrección.

Se ha publicado una interesante entrada en el blog GLL en la que hablan sobre este  mismo tema

The issue is simple:

Someone writes up a paper that “proves” that X is true, where X is some hard open problem. How do we check that X is proved?

The proof in question is almost always long and complex. So the checking is not a simple matter. In some cases the proof might even use nonstandard methods and make it even harder to understand.

y comentan sobre las posibles reacciones a este nuevo estilo de matemáticas.  Recomendamos su lectura.

(more…)

Algorítmica y complejidad computacional. Otra conjetura (dicotomia Feder-Vardi en CSPs) posiblemente resuelta.

enero 12, 2017

Es el nuevo estilo de publicación: sin estar seguro de que lo que se tiene entre manos y publica es 100% correcto. Al igual que los problemas que se intentan resolver, las demostraciones son cada vez más complejas y necesitan múltiples mentes para la comprobación de su corrección.

Me interesé en las dicotomías relacionadas con CSP en su momento, cuando estudiaba sobre temas de complejidad computacional. Esta dicotomía además tiene que ver con digrafos, en los que tenemos interés en general. Y para más inri tiene que ver con homomorfismos entre digrafos y uno de los pasos de nuestro método es precisamente un homomorfismo entre digrafos. Por lo tanto vamos a hacer seguimiento. Pero ojo, no estamos afirmando que este resultado tenga nada que ver con el nuestro.

El artículo:  Dichotomy for Digraph Homomorphism Problems

We consider the problem of finding a homomorphism from an input digraph G to a fixed digraph H. We show that if H admits a weak-near-unanimity polymorphism ϕ then deciding whether G admits a homomorphism to H (HOM(H)) is polynomial time solvable. This confirms the conjecture of Bulatov, Jeavons, and Krokhin, in the form postulated by Maroti and McKenzie, and consequently implies the validity of the celebrated dichotomy conjecture due to Feder and Vardi. We transform the problem into an instance of the list homomorphism problem where initially all the lists are full (contain all the vertices of H). Then we use the polymorphism ϕ as a guide to reduce the lists to singleton lists, which yields a homomorphism if one exists.

el blog dónde he visto la noticia.

Algorítmica y complejidad computacional. El problema P vs. NP, un survey.

enero 8, 2017

El autor del survey es el merecidamente popular bloguero (y por supuesto académico experto en computación cuántica) Aaronson.

Lo he leído muy muy en diagonal este finde aprovechando que tenía un potente resfriado, lo cual en general y paradójicamente me inspira. Me ha gustado sobre todo (y mucho) el punto 6, en el que he concentrado mi tiempo. Los otros puntos, que finalmente me he saltado, diría que no aportan demasiado a cualquiera que ya conozca el tema (aunque yo lo tengo completamente oxidado y me vendría bien un recordatorio, así que lo leeremos más detalladamente en otra ocasión).

El punto 6 repasa las barreras o limitaciones teóricas que se han encontrado (y se pueden encontrar) en los intentos de demostraciones de esta conjetura (tema muy bien explicado que finalmente creo que he comprendido, pero que nadie me pida que se lo explique ahora :-); nos demuestran que hay niveles de abstracción inadecuados o más bien insuficientes para atacar este problema, sea por exceso o sea por defecto, lo cual da que pensar; realmente los nombres elegidos para las denominarlas no dicen mucho de lo que luego son) así como algunos enfoques prometedores, que permiten saltarse estas barreras (aunque a lo mejor se encontrarán con otras) como el utilizar cotas superiores algorítmicas para demostrar cotas  inferiores teóricas y así separar clases de complejidad (método que ya ha dado sus frutos hace unos años, separando dos clases de complejidad, eso sí muy extremas; también tiene un nombre raro) o el enfoque llamado Geometric Complexity Theory que aplica técnicas de geometría algebraica (el estudio de los conjuntos de soluciones de los sistemas de ecuaciones algebraicases decir a ecuaciones polinómicas multivariables, cuando las variables recorren determinados tipos de estructuras algebraicas) a estos temas. Gracias a este survey también he comprendido este último enfoque, obviamente en líneas muy muy generales (idem, que  nadie me pida que se lo explique…).  El autor no entra en demasiados detalles técnicos al respecto, lo cual algunos agradecerán, pero nos da una visión de (un) pájaro con muy buena vista. Por lo visto a algunos expertos este enfoque les parece una complicación innecesaria; a otros un camino viable.

Espero lector, que disfrutes del  survey.

Por cierto, al leerlo me he acordado de un tema que tenemos pendiente de comprobar con respecto a nuestro método de demostración de no hamiltonicidad en casos, que bien por ser entangled o twisted, no tienen recorridos hamiltonianos, método que hemos detallado largamente en varias entradas el pasado verano: ¿ como escala este método con el tamaño del input ?.

Ya en el peor caso, sólo determinar o decidir si un caso es entangled puede ser subexponencial (cota de Landau). Si es entangled el caso es potencialmente complicado y ya podemos decidir abandonarlo sin más e identificar otro que sea potencialmente sencillo.

Pero si por los motivos que sean nos gustan sus propiedades conocidas y además queremos que tenga recorridos hamiltonianos luego hay una serie de pasos más que nos permiten demostrar que no los tiene y aplicar el  razonamiento contrapositivo, según hemos detallado en las entradas del año pasado. Así de memoria pensamos no incrementarán la cota teórica señalada en el peor caso (según pienso hablaríamos de una suma de operaciones de complejidad subexponencial, lo cual sólo añadiría constantes). Pero queremos comprobarlo.

De  cualquier manera ya la cota subexponencial peor caso sólo para decidir si el caso es entangled nos deja completamente insatisfechos…Por otra parte también hemos comentado en varias entradas anteriores que hay buenos argumentos para pensar que el caso medio no será subexponencial, sino más bien cuasipolinómico (ver también aquí), lo cual nos consuela. Por otra parte de momento no hemos investigado si hay un test más eficiente para identificar si un caso tiene las propiedades de entrelazado (entanglement) o de retorcimiento (twistedness). No me parece fácil mejorar el  estado del arte en esto, pero tampoco imposible.

Algunos extractos (barriendo para casa :-)):

 –2.2.1 Search, Decision, and Optimization . . . . . . . . . . . . . . . . . . . . . . . . 16

Es un extracto del índice. En el punto indicado nos explica la diferencia entre estos problemas (también la no diferencia desde el punto de vista de complejidad computacional). ¿ Por qué es tan complicado entender esta diferencia ?

–Just as Hilbert’s question turned out to have a negative answer, so too in this case, most computer scientists conjecture that P!= NP: that there exist rapidly checkable problems that aren’t rapidly solvable, and for which brute-force search is close to the best we can do. This is not a unanimous opinion. At least one famous computer scientist, Donald Knuth [151], has professed a belief that P = NP, while another, Richard Lipton [171], professes agnosticism.   

Desconocía esta posición de Knuth tan extrema (bastante reciente; la referencia es: D. E. Knuth and E. G. Daylight. Algorithmic Barriers Falling: P=NP? Lonely Scholar, 2014; se trata de una entrevista). Si conocía la del otro investigador pues leemos su blog. Son, dicho sea con todos los respetos, dos veteranos que ya no tienen nada que demostrar a nadie ni nada que temer y, a calzón quitao, muestran un escepticismo a contracorriente muy sano y recomendable, que equilibra la balanza. Hace poco hicimos una entrada sobre otro investigador, más joven, que también expresaba sus dudas abiertamente.

–More broadly, there are many cases in mathematics where we can prove that some object O of interest to us has a property P, even though we have no hope of finding a general polynomial time algorithm to decide whether any given object has property P, or even to certify a large fraction of objects as having property P. In such cases, often we prove that O has property P by exploiting special symmetries in O—symmetries that have little to do with why O has property P, but everything to do with why we can prove it has the property. As an example, a random graph is an expander graph (that is, a graph on which a random walk mixes rapidly) with overwhelming probability. But since the general problem of deciding whether a graph is an expander is NP-hard, if we want a specific graph G that’s provably an expander, typically we need to construct G with a large amount of symmetry: for example, by taking it to be the Cayley graph of a finite group. Similarly, even though we expect that there’s no general efficient algorithm to decide if a Boolean function f is hard,51 given as input f’s truth table, we might be able to prove that certain specific f’s (for example, NP- or #P-complete ones) are hard by exploiting their symmetries. Geometric Complexity Theory (see Section 6.6) is the best-known development of that particular hope for escaping the natural proofs barrier.

Esta es la única mención honorífica a los Grafos de Cayley en todo el survey, en un contexto perfectamente conocido desde hace años. Pero lo hemos extractado sobre todo porque es una prueba más del hecho de que demostrar que un grafo tiene determinadas propiedades, y sólo esto, añade valor. Cosa que de nuevo parece que a algunos les cuesta comprender.

–ETH is an ambitious strengthening of P!= NP. Even assuming P!= NP, there’s by no means a consensus in the field that ETH is true—let alone still further strengthenings, like the Strong Exponential Time Hypothesis or SETH, which asserts that any algorithm for kSat requires Ω ((2 − ε) n ) time, for some ε that goes to zero as k → ∞. SETH, of course, goes even further out on a limb than ETH does, and some algorithms researchers have been actively working to disprove SETH (see [275] for example).

En el blog nos hemos interesado bastante por la conjetura ETH hace años.

–But now we come to the main insight of GCT, which is that the permanent and determinant are both special, highly symmetric functions, and it’s plausible that we can leverage that fact to learn more about their orbit closures than we could if they were arbitrary functions. For starters, Per (X) is symmetric under permuting X’s rows or columns, transposing X, and multiplying the rows or columns by scalars that multiply to 1. That is, we have

Per (X) = Per ( XT ) = Per (P XQ) = Per (AXB) (2)

for all permutation matrices P and Q, and all diagonal matrices A and B such that Per (A) Per (B) = 1.

The determinant has an even larger symmetry group: we have

Det (X) = Det ( XT ) = Det (AXB) 

Nos gusta la simetría. Muy interesante. En esto se basa todo el enfoque GCT, al parecer.

Algorítmica y Complejidad Computacional. Recopilación de enlaces, noviembre 2016: Redes de Interconexión, Grafos de Cayley, Recorridos Hamiltonianos, Permutaciones y otros. 

noviembre 30, 2016

Una recopilación de artículos sobre los temas que aparecen en el título, realizada en fechas varias, la última esta misma mañana (por el lunes), en la cual he encontrado cosas muy interesantes con respecto a potenciales aplicaciones. Aunque ya se sabe que entre la ingeniería apegada a la tierra y las elevadas matemáticas se encuentra el limbo de potenciales aplicaciones que nunca terminarán de concretarse en sistemas reales.

Antes de empezar con los enlaces un extracto de una muy reciente entrada en un blog de un experto en complejidad computacional. Creo que es reseñable ya que la declaración es sorprendente, contundente y va contracorriente:

The bottom line of this post is that we can’t prove lower bounds because they are false, and it is a puzzle to me why some people appear confident that P is different from NP.

Añadido a última hora.

On the Complexity of the Word Problem of Automaton Semigroups and Automaton Groups

I. Enfoque de ingeniería de redes: redes de interconexión (supercomputadores, NoC´s, Data Center Networks).

Data center interconnection networks are not hyperbolic

David Coudert1,2 and Guillaume Ducoffe2,1 1 Inria, France 2Univ. Nice Sophia Antipolis, CNRS, I3S, UMR 7271, 06900 Sophia Antipolis, France

Abstract Topologies for data center networks have been proposed in the literature through various graph classes and operations. A common trait to most existing designs is that they enhance the symmetric properties of the underlying graphs. Indeed, symmetry is a desirable property for interconnection networks because it minimizes congestion problems and it allows each entity to run the same routing protocol. However, despite sharing similarities these topologies all come with their own routing protocol. Recently, generic routing schemes have been introduced which can be implemented for any interconnection networks. The performances of such universal routing schemes are intimately related to the hyperbolicity of the topology. Roughly, graph hyperbolicity is a metric parameter which measures how close is the shortest-path metric of a graph from a tree metric (the smaller gap the better). Motivated by the good performances in practice of these new routing schemes, we propose the first general study of the hyperbolicity of data center interconnection networks. Our findings are disappointingly negative: we prove that the hyperbolicity of most data center topologies scales linearly with their diameter, that it the worst-case possible for hyperbolicity. To obtain these results, we introduce original connection between hyperbolicity and the properties of the endomorphism monoid of a graph. In particular, our results extend to all vertex and edge-transitive graphs. Additional results are obtained for de Bruijn and Kautz graphs, grid-like graphs and networks from the so-called Cayley model.

–Muy interesante. Y muy reciente, de 2016.

The Influence of Datacenter Usage on Symmetry in Datacenter Network Design

Alejandro Ericksona , Iain A. Stewarta,∗ aSchool of Engineering and Computing Sciences, Durham University, South Road, Durham DH1 3LE, U.K.

Abstract We undertake the first formal analysis of the role of symmetry, interpreted broadly, in the design of server-centric datacenter networks. Although symmetry has been mentioned by other researchers, we explicitly relate it to various specific, structural, graph-theoretic properties of datacenter networks. Our analysis of symmetry is motivated by the need to ascertain the usefulness of a datacenter network as regards the support of network virtualization and prevalent communication patterns in multi-tenanted clouds. We argue that a number of structural concepts relating to symmetry from general interconnection networks, such as recursive-definability, the existence and dynamic construction of spanning-trees, pancyclicity, and variations of Hamiltonicity, are appropriate topological metrics to use in this regard. In relation to symmetry, we highlight the relevance of algebraic properties and algebraic constructions within datacenter network design. Built upon our analysis of symmetry, we outline the first technique to embed guest datacenter networks in a host datacenter network that is specifically oriented towards server-centric datacenter networks. In short, we provide the graphtheoretic foundations for the design of server-centric datacenter networks so as to support network virtualization and communication patterns in cloud computing.

Extractos.

Whilst the design of DCNs is more recent, it has much in common with general interconnection network design yet there are profound differences too, prompted by, for example, usage, scale, and packaging. Hitherto, the most common metrics used for DCN evaluation are the availability of routing algorithms, hardware cost (e.g., number of servers and switches), hardware complexity (e.g., number of server-ports), diameter, bisection width, connectivity, and shortest-path lengths. It is probably fair to say that the development of appropriate topological metrics for DCNs is not as advanced as it is for distributed-memory multiprocessors and networks-onchips, and that the validity of these topological metrics within a datacenter environment is not as well established. Our paper seeks to strengthen the role of topological metrics in DCN design.

Our work sits between the engineering process of building datacenters and the theoretical consideration of abstractions of DCNs as discrete structures; that is, it is graph theory targetted towards a practical application area.

(more…)

La IP. ¿?

octubre 13, 2016

¿¿¿

entusiasmado

 

 

 

 

 

???

(more…)