¿Hay alguna con las siguientes propiedades:L ∈ N PL∈NPL\in {\bf NP} Se sabe que implica P = N P .L ∈ PL∈PL\in {\bf P}P = N PP=NP{\bf P}={\bf NP} No hay (conocido) tiempo polinómico reducción Turing de (o algún otro N P problema -Complete) a L .SA TSATSATN PNP{\bf NP}LLL En otras palabras, si un...
Todos mis libros de texto usan el mismo algoritmo para producir un DFA dado un regex: primero, haga un NFA que reconozca el idioma del regex, luego, usando la construcción del subconjunto (también conocido como "powerset"), convierta el NFA en un DFA equivalente ( opcionalmente minimizando el DFA)....
En 1996, un problema abierto de larga data fue resuelto por una computadora; a saber, que el álgebra de Robbins y el álgebra booleana son lo mismo. La prueba fue encontrada por un probador de teoremas automatizado. Además, la prueba conocida del teorema de cuatro colores contiene componentes...
¿Es este juego de información perfecto jugado en gráficos conocido / estudiado? Dado un gráfico G=(V,E)G=(V,E)G= (V,E) , dos jugadores se alternan eligiendo un borde o un nodo aislado. Si el jugador elige un borde e=(u,v)e=(u,v)e = (u,v) los dos nodos uuu y vvv se eliminan junto con sus bordes...
Estoy buscando problemas NP-hard para una reducción. Hasta ahora he encontrado los siguientes problemas: Problema de 3 particiones problema de embalaje Emparejamiento numérico tridimensional TSP Cualquier problema de NP completo sin datos numéricos, por ejemplo, SATISFIABILIDAD, CICLO...
Dados dos subconjuntos del hipercubo dimensional (es decir, M , N ⊆ { 0 , 1 } d ), estoy buscando un algoritmo que recupere los puntos m ∈ M , n ∈ N st la distancia de Hamming (o L 1 - distancia en el hipercubo) d H ( m , n ) es mínima. El ingenuo algoritmo que verifica cada par necesita | M | ⋅ |...
En cs.stackexchange , pregunté sobre la biblioteca algebird scala en github, especulando sobre por qué podrían necesitar un paquete de álgebra abstracta. La página de github tiene algunas pistas: Implementaciones de monoides para algoritmos de aproximación interesantes, como el filtro Bloom,...
Estoy buscando una estructura de datos y un algoritmo para calcular la cantidad mínima de cambios necesarios para transformar una palabra en otra, dadas las dos palabras como entradas, donde los únicos cambios permitidos son agregue una letra en una de las extremidades (por ejemplo, AB ->...
Tengo algunas preguntas sobre engañar a los circuitos de profundidad constante. Se sabe que la independencia de es necesaria para engañar a los circuitos A C 0 de profundidad d , donde n es el tamaño de la entrada. ¿Cómo se puede probar esto?Iniciar sesiónO ( d)( n )logO(d)(n)\log^{O(d)}(n)A C0...
Estoy tratando de entender el protocolo bitcoin en el contexto de la seguridad criptográfica computacional. La pregunta es una solicitud de referencia a fundamentos de artículos de criptografía sobre bitcoin. Mi primera pregunta es ¿qué protocolo criptográfico abstracto está intentando...
Me gustaría saber si existe un mundo donde relativizada . También estoy interesado en saber si existe un mundo donde relativizada P B ≠ N P B = P P B .PAGUNA= N PUNA≠ P PUNAPA=NPA≠PPA{\bf P^A}={\bf NP^A}\not = {\bf PP^A}PAGsi≠ N Psi= P PsiPB≠NPB=PPB{\bf P^B} \not = {\bf NP^B} = {\bf...
Aproximadamente una matriz de rango se dice que es rígida, si se baja su rango a nnnn , uno tiene que cambiar al menosn1+ϵde sus entradas, para algunosϵ>0.n2n2\frac{n}{2}n1+ϵn1+ϵn^{1+\epsilon}ϵ>0ϵ>0\epsilon > 0 Si una matriz A es rígida, entonces el programa de línea recta más pequeño que...
Yo, como muchas personas, soy un usuario entusiasta de software matemático como Mathematica y Maple. Sin embargo, me siento cada vez más frustrado por los muchos casos en que dicho software simplemente le da la respuesta incorrecta sin previo aviso. Esto puede ocurrir al realizar todo tipo de...
Deja ad(G)ad(G)\rm{ad}(G) sea la distancia media de un gráfico conectado G.G.G. Una forma de calcular ad(G)ad(G)\rm{ad}(G) es sumar los elementos de D(G),D(G),D(G), la matriz de distancia de GGG y escalar la suma adecuadamente. Si el gráfico de salida es un árbol, entonces se sabe que la...
El asistente de enseñanza de un curso ha logrado escribir un programa que (determinísticamente) genera preguntas de examen difíciles. Ahora, le gustaría escribir un programa que genere las respuestas correspondientes. El problema del examinador pregunta si esto siempre es posible; la conjetura de...
Estoy tratando de entender la relación entre la complejidad algorítmica y la complejidad del circuito de los determinantes y la multiplicación de matrices. Se sabe que el determinante de una matriz se puede calcular en el tiempo , donde es el tiempo mínimo requerido para multiplicar dos matrices....
Se sabe que algunas clases de complejidad sintáctica (no relativizadas) entre y P S P A C E tienen la siguiente propiedad, P ⊆ C o N P ⊆ U S ⊆ C = P ⊆ P P ⊆ P S P A C E . Me pregunto si existe una clase de complejidad sintáctica (no relativizada) X tal que P P ⊆ X ⊆ P S P A C EPP{\bf...
Este es un seguimiento de mi pregunta anterior: Mejor complejidad de tiempo determinista conocida límite inferior para un problema natural en NP Me resulta desconcertante que no hayamos podido probar ningún límite inferior de tiempo determinista cuadrático para ningún problema interesante de NP...
Parte de la dificultad de obtener más información sobre este problema es que el problema de coincidencia de gráficos es diferente de su primo mucho más famoso, el problema de coincidencia, pero es difícil distinguirlo cuando se utilizan motores de búsqueda. Dados dos gráficos y modo que, la tarea...
Si bien la regla general es que en los documentos de TCS los autores están ordenados alfabéticamente, hay algunos contraejemplos notables que vienen a la mente, en los que los autores están ordenados de una manera diferente, por ejemplo, Métodos algebraicos para sistemas de prueba interactivos...