Supongamos que . N P I es la clase de problemas en que no están ni en ni en N P -hard. Puede encontrar una lista de problemas conjeturados como N P I aquí .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}NPINPI\mathsf{NPI}PNPNP\mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}NPINPI\mathsf{NPI} El teorema de Ladner nos...
Sabemos que los colorantes de borde de un gráfico son colorantes de vértices de un gráfico especial, a saber, de la gráfica de línea L ( G ) de G .solsolG L(G)L(G)L(G)GGG ¿Hay un operador de gráfico ΦΦ\Phi tal que los colores de vértice de un gráfico GGG son colores de borde del gráfico...
Se sabe que se puede calcular exactamente el determinante de una matriz en el espacio determinístico log 2 ( n ) . ¿Cuáles serían las implicaciones de complejidad de aproximar el determinante de una matriz real, de la norma como máximo 1 ( ‖ A ‖ ≤ 1 ) en el espacio logarítmico aleatorizado, por...
Un nuevo artículo salió reclamando algoritmo cuasi-polinomial para Logarithm discreto. http://arxiv.org/abs/1306.4244 Si es correcto, ¿significa que ya no tenemos una separación exponencial en la complejidad de un algoritmo clásico y su versión cuántica para el problema del logaritmo discreto?...
Me pregunto, ¿hay algún trabajo o investigación que trate con autómatas visiblemente pushdown, pero que permita que las palabras, en lugar de letras simples, sean empujadas a la pila. Alternativamente, una construcción que permita que los símbolos se presionen en las transiciones ϵϵ\epsilon podría...
Cualquier gráfico plano , respectivamente, externo-plano satisfaceG=(V,E)G=(V,E)G=(V,E)|E′|≤3|V′|−6|E′|≤3|V′|−6|E'|\le 3|V'|-6 , respectivamente, , para cada subgrafo G ′ = ( V ' , E ' ) de G . Además, las gráficas planas (externas) se pueden reconocer en tiempo...
En el artículo An Efficient Algorithm for Graph Isomorphism de Corneil y Gotlieb, 1970, se estableció una conjetura en la que se basó el algoritmo para resolver GI en el tiempo polinomial. A saber: que los gráficos representativos exhiben la división de automorfismo del gráfico...
Esta pregunta probablemente esté en el límite entre el tema y fuera del tema, sin embargo, he visto preguntas similares aquí, por lo tanto, lo haré. Estoy implementando un solucionador Unique -SAT, cuya entrada es una fórmula -CNF que tiene como máximo asignación satisfactoria. Para probar su...
Me ofrecieron enseñar un nuevo programa de escuela secundaria TCS, que requiere la construcción de un plan de estudios. Me gustaría mucho escuchar opiniones y sugerencias sobre esto. Primero, ¿alguien sabe de las escuelas secundarias donde se ha enseñado un programa TCS con éxito (o sin...
Hay muy poca información que puedo encontrar sobre el problema NP-completo de resolver la ecuación lineal de diofantina en enteros no negativos. Es decir, ¿hay una solución en no negativo para la ecuación , donde todas las constantes son positivas? La única mención notable de este problema que...
Gowers ha esbozado recientemente un problema, que él llama "determinación Borel discreta", cuya solución está relacionada con probar los límites inferiores del circuito. ¿Puede proporcionar un resumen del enfoque que se adapta a una audiencia de teóricos de la complejidad? ¿Qué se necesitaría...
Los autómatas finitos no ambiguos (UFA) son un tipo especial de autómatas finitos no deterministas (NFA). Un NFA se llama inequívoco si cada palabra tiene como máximo una ruta de aceptación.w ∈ Σ∗w∈Σ∗w\in \Sigma^* Esto significa .D FA ⊂ UFA ⊂ NFUNreFUN⊂UFUN⊂norteFUNDFA\subset UFA\subset...
Estoy buscando problemas que se sabe que son NPC para gráficos dirigidos pero tienen un algoritmo polinomial para gráficos no dirigidos. He visto la pregunta sobre los problemas "dirigidos" al revés que son más fáciles que su variante "no dirigida" , pero estoy buscando dureza en el lado...
Cuando miramos el libro, Teoría del tipo de homotopía , vemos los siguientes temas: Homotopy type theory 2.1 Types are higher groupoids 2.2 Functions are functors 2.3 Type families are fibrations 2.4 Homotopies and equivalences 2.5 The higher groupoid structure of type formers 2.6 Cartesian...
Los teoremas de la jerarquía son herramientas fundamentales. Un buen número de ellos se recopiló en una pregunta anterior (consulte ¿Qué jerarquías y / o teoremas de jerarquía conoce? ). Algunas separaciones de clase de complejidad se derivan directamente de los teoremas de jerarquía. Ejemplos de...
Una cubierta de borde es un subconjunto de bordes de un gráfico de tal manera que cada vértice del gráfico es adyacente al menos a un borde de la cubierta. Los siguientes dos artículos dicen que las cubiertas de borde de conteo, se #P -Complete: A FPTAS simples para el recuento de cubiertas de...
¿Está NP en DTIME(npolylogn)DTIME(npolylogn)DTIME(n^{poly\log n})
Me interesa si existen buenos artículos o encuestas expositivas a los que me pueda referir cuando escribo sobre operadores de clase de complejidad : operadores que transforman las clases de complejidad haciendo cosas como agregarles cuantificadores. Ejemplos de operadores. Lo siguiente se puede...
Estoy tratando de entender la complejidad de las funciones que se expresan a través de las puertas de umbral y esto me llevó a . En particular, estoy interesado en lo que se sabe actualmente sobre el aprendizaje dentro de T C 0 , ya que no soy un experto en el
Disculpas si esta es una pregunta demasiado amplia para este foro, pero estoy interesado en tácticas y consejos específicos que los investigadores (en TCS) usan para escribir la introducción de un trabajo de investigación.