Tenemos un problema y encontramos un algoritmo que parece ser 2-nexptime. Me gustaría encontrar problemas conocidos de 2-nexptime-complete para encontrar un límite inferior. Encontré en la literatura principalmente dos de estos problemas: si PCP como solución de tamaño inferior a...
El tiempo cuasi polinomial, o QP para abreviar, es una clase de complejidad en la máquina determinista de Turing. Aquí está la definición precisa: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp Mientras que βP es una clase de complejidad de no determinismo limitado. Aquí está la definición...
Se sabe que el problema # MONOTONE-2SAT es # P-completo. Esto significa que #SAT se puede reducir a eso. Mi pregunta es: dada una instancia #SAT , ¿cuál es la transformación que convierte F en su correspondiente instancia # MONOTONE-2SAT F ' ?FFFFFFF′F′F' Una segunda pregunta es: que es el número...
¿Se sabe si SPACE (n) (la clase de lenguajes reconocidos por TM deterministas con espacio lineal) es un subconjunto apropiado de E (la clase de lenguajes reconocidos por TM deterministas en el tiempo 2 ^ O
Esta es una pregunta algo frívola que surgió en mi cabeza después de leer las diversas respuestas a "¿Cuál es la clase de complejidad" más pequeña "para la que se conoce un circuito superlineal? ". Las respuestas se refieren a , y cuando miré la entrada del zoológico , descubrí...
por favor, ¿puede proporcionar una referencia o dar ejemplos particulares de problemas completos de PSPACE que se puedan resolver en tiempo pseudo-polinomial? Notas Adicionales: Definición de tiempo pseudopolinomial: http://en.wikipedia.org/wiki/Pseudo-polynomial_time En respuesta a algunos...
Como sabemos, el isomorfismo gráfico está en NP pero no se sabe que sea NP-Completo o P-Completo. Me preguntaba si hay algún problema que se sabe que está en PSPACE pero no se sabe que es PSPACE-Complete y no se encuentra en
¿Existe una función similar a una trampilla cuya complejidad de codificación es el tiempo polinomial nk1nk1n^{k_{1}} y la complejidad inversora (sin clave secreta) también es una función polinómica en la longitud de entrada con (digamos que y es incondicionalmente demostrable estar limitado por )...
¿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...
¿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...
Espero que esta pregunta no sea demasiado ingenua para este sitio. En matemáticas (topología, geometría, álgebra) es común que uno distinga entre dos objetos creando un invariante algebraico o numérico, y demostrando que los dos objetos tienen valores diferentes. Me pregunto hasta qué punto se ha...
Para poder explicar el problema P vs NP a los no matemáticos, me gustaría tener un ejemplo pedagógico de cuándo se puede evitar la búsqueda de fuerza bruta. Idealmente, el problema debería ser inmediatamente comprensible y el truco no debería ser ni demasiado fácil ni demasiado difícil. Lo mejor...
(Publiqué esta pregunta en CS hace diez días, sin respuesta desde entonces, así que la publico aquí). Cualquier fórmula CNF se puede transformar en tiempo polinómico en una fórmula 3-CNF mediante el uso de nuevas variables. No siempre es posible si no se permiten nuevas variables (tome por ejemplo...
Según Handshaking Lemma: cualquier gráfico no dirigido que tenga un vértice cuyo grado sea un número impar debe tener algún otro vértice cuyo grado sea un número impar. Esta observación significa que si se nos da un gráfico y un vértice de grado impar, y se nos pide que encontremos algún otro...
Estoy buscando más problemas en con límites inferiores de complejidad temporal clásica. Algunas personas podrían preguntarse cómo podría probar un límite tan bajo. Vea abajo.PPP Límites inferiores exponenciales: Reclamación: Si tiene un problema que es E X P T I M E -completo bajo reducciones...
En https://en.wikipedia.org/wiki/Geometric_complexity_theory se menciona que ".. Ketan Mulmuley cree que el programa, si es viable, es probable que tome alrededor de 100 años antes de que pueda resolver el problema P vs. NP". Parece indicar que el único programa actualmente viable podría enfrentar...
¿Puede la intersección de dos idiomas en NP que no son NP completos ser NP completos? ¿Se puede completar la intersección de dos idiomas en coNP que no están completos en coNP? ¿Puede la intersección de dos idiomas uno en coNP pero no completo y otro en NP pero no NP completo ser NP completo o...
Las versiones no uniformes de P, NP y coNP son P / poly, NP / poly y coNP / poly. Del mismo modo, podemos definir una versión no uniforme para cada nivel en el PH. Por ejemplo: / poly consiste en problemas de la forma , donde C es un circuito de tamaño polinómico que puede variar según la longitud...
Antecedentes Sabemos que .P#P⊆PSPACEP#P⊆PSPACEP^{\#P} \subseteq PSPACE Además, se conoce a partir del teorema de Toda que .PH⊆P#PPH⊆P#PPH \subseteq P^{\#P} Para obtener más información sobre , consulte aquí: https://en.wikipedia.org/wiki/Sharp-P#P#P\#P Pregunta ¿Existe un oráculo...
El lenguaje Critical SAT se define como el conjunto de fórmulas booleanas f tal que f ∈ U N S A T, pero eliminar cualquier cláusula de f lo hace satisfactorio. Se sabe que el SAT crítico es D P -completo. Me pregunto acerca de la siguiente variante: dada una fórmula C N F f , ¿es el caso que f está...