El problema de la suma de las raíces cuadradas pregunta, dadas dos secuencias y b 1 , b 2 , ... , b n de enteros positivos, si la suma ∑ i √a1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_nb1,b2,…,bnb1,b2,…,bnb_1, b_2, \dots, b_n menor que, igual o mayor que la suma∑i√∑iai−−√∑iai\sum_i \sqrt{a_i} . El...
Este problema está inspirado en esta pregunta de MO , que me pareció muy interesante. ¿Cuál es el problema abierto más antiguo en TCS? Claramente esta pregunta necesita alguna aclaración. Primero, ¿qué es TCS? Creo que la existencia de números perfectos impares no es TCS. Yo diría que el...
En la introducción y explicación, las clases de complejidad P y NP a menudo se dan a través de la máquina Turing. Uno de los modelos de computación es el cálculo lambda. Entiendo que todos los modelos de computación son equivalentes (y si podemos introducir algo en términos de máquina de Turing,...
En general, sabemos que la complejidad de probar si una función toma un valor particular en una entrada dada es más fácil que evaluar la función en esa entrada. Por ejemplo: Evaluar el permanente de una matriz entera no negativa es # P-hard, pero determinar si dicho permanente es cero o no está...
Suponga que los coautores de dos o más instituciones diferentes están escribiendo un artículo en látex, y les gustaría hacerlo mejor que enviar borradores repetidamente por correo electrónico. Se dan cuenta de que pueden abrir de forma gratuita una cuenta de Dropbox, compartir la contraseña y...
¿Cuál es el límite superior en el algoritmo simplex para encontrar una solución a un programa lineal? ¿Cómo haría para encontrar una prueba para tal caso? Parece que el peor de los casos es si cada vértice tiene que ser visitado, es decir, . Sin embargo, en la práctica, el algoritmo simplex se...
Decidir si existe un equilibrio de Nash es fácil (siempre existe); sin embargo, se cree que encontrar uno es difícil (es PPAD-Complete). ¿Cuáles son algunos otros ejemplos de problemas en los que la versión de decisión es fácil pero la versión de búsqueda es relativamente difícil (en comparación...
Pregúntele incluso a alguien con experiencia en informática qué es una expresión regular, y es probable que la respuesta vaya más allá de la restricción de estar al alcance de un autómata de estado finito. Por ejemplo, la "expresión regular" /^1?$|^(11+?)\1+$/ creado por la destacada...
Tengo curiosidad por saber si hay una manera de almacenar un hash de un conjunto múltiple de enteros que tenga las siguientes propiedades, idealmente: Utiliza el espacio O (1) Se puede actualizar para reflejar una inserción o eliminación en tiempo O (1) Dos colecciones idénticas (es decir,...
Esta pregunta está dirigida a personas que asignan problemas: maestros, asistentes de estudiantes, tutores, etc. Esto me ha sucedido varias veces en mis 12 años de carrera como profesor: rápidamente asigné algún problema del texto pensando "esto se ve bien". Luego me di cuenta de que no podía...
Sabemos que la función exponencial sobre números naturales no es computable en tiempo polinómico, porque el tamaño de la salida no está polinomialmente limitado en el tamaño de las entradas.exp(x,y)=xyexp(x,y)=xy\exp(x,y) = x^y ¿Es esta la razón principal de la dificultad de calcular la función...
Actualmente estoy comenzando en la universidad [informática] y allí tenemos muchas oportunidades para comenzar a investigar. Antes de encontrar este sitio web, no tenía intención de seguir este camino [quería trabajar con IA, probablemente desarrollador de juegos], pero ahora puedo [o necesito]...
Se conjetura que la aleatoriedad no extiende el poder de los algoritmos de tiempo polinomiales, es decir, se conjetura que P=BPPP=BPP{\bf P}={\bf BPP} se mantiene. Por otro lado, la aleatoriedad parece tener un efecto bastante diferente en las reducciones de tiempo polinomiales . Por el conocido...
Una aplicación importante del teorema de PCP es que produce resultados de tipo "dureza de aproximación". En algunos casos relativamente más simples, se puede demostrar tal dureza sin PCP. Sin embargo, ¿existe algún caso en el que el resultado de la dureza de la aproximación se haya probado por...
Estoy buscando una fuente de grandes conjuntos de datos para probar la implementación de algoritmos gráficos. Proporcione también información sobre el tipo / distribución (por ejemplo, dirigida / no dirigida, simple / no simple, ponderada / no ponderada) de los gráficos en la fuente si se...
Esta es una pregunta no técnica, pero ciertamente relevante para la comunidad TCS. Si se considera inapropiado, no dude en cerrar. La página web de Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo) ciertamente ha sido de gran servicio para la comunidad de TCS a lo largo de los...
Antecedentes: la motivación para esta pregunta es doble. Primero, me gustaría obtener algunos datos concretos para comprender mejor las conferencias en curso frente al debate de las revistas . Segundo, si esta información estuviera disponible en algún lugar, podría tomar una decisión más informada...
Dado un nuevo problema en NPNP\mathsf{NP} cuya verdadera complejidad está en algún lugar entre y NP-complete, hay dos métodos que sé que podrían usarse para demostrar que resolver esto es difícil:PP\mathsf{P} Demuestre que el problema es GI completo (GI = isomorfismo gráfico) Muestre que el...
Por lo tanto, los filtros Bloom son bastante geniales: son conjuntos que admiten la verificación de membresía sin falsos negativos, pero con una pequeña posibilidad de un falso positivo. Recientemente, sin embargo, he estado buscando un "filtro Bloom" que garantice lo contrario: sin falsos...
Sea una gráfica con la función de peso . El problema de max-cut es encontrar: If la función de peso no es negativa (es decir, w (e) \ geq 0 para todas las e \ en E ), entonces hay muchas aproximaciones de 2 extremadamente simples para max-cut. Por ejemplo, podemos:G=(V,E,w)G = (V, E,...