Cuando aprendemos problemas de optimización, generalmente consideramos la programación lineal (o más generalmente: optimización convexa) como el ejemplo más simple. Es solucionable en tiempo polinómico y tiene algoritmos relativamente fáciles de entender. Sin embargo, la versión de decisión de LP...
Deje que e sean conjuntos, y sea una partición de . Me gustaría demostrar que existe una distribución sobre cuyo marginal es uniforme sobre , y tal que la distribución sobre inducida por tiene una gran entropía (el esta última distribución se define asignando a cada la masa de probabilidad total de...
Estoy buscando una solución al siguiente problema y me pregunto si alguien podría señalarme alguna investigación existente sobre este tema. Vengo de una aplicación de gráficos del mundo real, así que tengan paciencia conmigo si mi terminología no es exactamente la correcta. Tengo un sistema de...
La clasificación mediante comparaciones de 2 elementos tiene una complejidad asintótica en el peor de los casos de nlog2(n)nlog2(n)n \log_2(n) (alcanzado por mergesort, heapsort, inserción binaria, ford-johnson al menos), lo cual es óptimo. Si ordenamos usando comparaciones que ordenan k...
¿Existen límites inferiores no triviales en el tiempo de ejecución de los algoritmos gráficos en RAM / PRAM / modelos de computación? No estoy buscando los resultados de NP-Hardness aquí. El siguiente es un resultado que pude encontrar [ver ref L92]: 3-Colorear un ciclo n requiere tiempo .Ω (...
¿Se sabe si el rango de tensor de los tensores tridimensionales se encuentra en VNP (clase valiente no determinista)? En caso afirmativo, ¿qué se sabe sobre el rango de tensor de alta dimensión? De hecho, estoy interesado en un problema mucho más simple. Me gustaría saber si se pueden construir...
Conozco las siguientes variantes de problemas SUBSETSUM: ( Elberfeld at. Al., 2010 ), NP-complete , y NEXP-complete ( enlace ).S U B S E T S U M S U C C I N C T - S U B S E T S U MUN A R Y - S UB S E T S UM∈LUNARY-SUBSETSUM∈L \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} SUBSETSUMETROSUBSETSUM...
Soy nuevo en el estudio de sistemas de reescritura como estudiante de doctorado de primer año. Me gustaría proponer un curso de temas especiales sobre la teoría de la reescritura, y quiero asegurarme de no dejar de lado ninguna de las fuentes originales. Tengo una copia de Barendregt y Terese como...
Considere un politopo racional que se define por medio de un oráculo de separación. Es decir, puede describirse implícitamente como , pero dado que es muy grande, utilizamos un oráculo, que da un punto , o bien dice o devuelve una media-espacio tal que .P P = { x ∈ R k : A x ≤ b , A ∈ Z m × k , b ∈...
¿Cuál es el conjunto más grande que admite un algoritmo de búsqueda cuántica determinista, para un solo elemento marcado, que opera con una sola llamada al oráculo? La pregunta es interesante ya que el algoritmo de Grover, que para la búsqueda no estructurada en un conjunto de elementos requiere O...
Supongamos que queremos encontrar el elemento más pequeño de un conjunto , cuyos elementos están indexados de a . No tenemos acceso a los valores de estos elementos, pero podemos comparar cualquiera de los dos elementos de para ver cuál es más pequeño. Para cualquier índices y , hay un asociado...
Estoy buscando fuentes sobre la noción formal de programas. Esto parece estar estrechamente relacionado con la correspondencia de Curry-Howard, pero también podría rastrearse hasta Universal Turing Machines y su capacidad para leer la descripción y la entrada de cualquier TM. Al leer sobre la...
Me gustaría saber la importancia de TCS en la investigación de malware. Debido al gran volumen de nuevas variantes de malware recibidas por día (~ 50,000 muestras / día según McAfee), los investigadores de malware dependen en gran medida del análisis dinámico (es decir, ejecutar las muestras en un...
¿Alguien sabe de algún trabajo que vincule la informática teórica y la energía barata / sostenible? es decir, ¿hay algún trabajo en TCS con la aplicación en energía barata /
¿Se sabe algo sobre lenguajes reconocidos por un autómata determinista bidireccional de múltiples cabezas o un logspace TM con contador (modelo equivalente)? Esta clase se llama Aux2DC en el documento de mi asesor . ¿O sobre tal clase no determinista? He obtenido que la clase de idiomas reconocidos...
¿El siguiente problema es NP-hard? Dado un conjunto de números reales (objetivos) x 1 , ... , x N y un "tridente" definido por dos distancias a , b desde el centro del tridente, ¿cuál es el número mínimo K de posiciones p 1 , ... , p K del tridente para cubrir todos los objetivos, es decir, K ⋃ k...
¿Es posible encontrar una reducción de conteo de #SAT a #HornSAT? No he encontrado esta pregunta publicada aquí, así que decidí verificar si alguien tiene alguna respuesta. Permítanme explicar a qué me refiero con contar la reducción. Suponga que son dos problemas de conteo. Por ejemplo, #SAT...
En mi trabajo surgió el problema de la clasificación CFL bajo imágenes de funciones racionales. En otros términos, ¿qué clase de lenguajes forman idiomas , para el contexto fijo lenguaje libre y el transductor de estados finitos determinista . He obtenido algunos resultados fáciles, como el...
Me gustaría un método eficiente para calcular la cantidad mínima de transposiciones necesarias para ordenar una lista. No necesito saber cuáles son las transposiciones en realidad. Por ejemplo, la lista [1, 1, 2, 0] requiere 2 transposiciones: [1, 1, 2, 0] // Start [1, 1, 0, 2] // Swap index 2...
Estaba leyendo sobre el problema de la altura de las estrellas y noté que la familia de expresiones regulares de Eggan sigue un patrón simple que puede describirse mediante una expresión regular. Mi pregunta es: ¿hay resultados interesantes sobre expresiones regulares que describan familias de...