Esperaba que alguien pudiera explicarme por qué exactamente el problema del producto del subconjunto es fuertemente NP-duro, mientras que el problema de la suma del subconjunto es débilmente NP-duro. Subconjunto Suma: Dada y , ¿existe un subconjunto tal que .X= { x1, . . . ,
Hice esta pregunta hace 10 días en cs.stackexchange aquí, pero no tenía ninguna respuesta. En un artículo muy famoso (en la comunidad de redes), Wang y Crowcroft presentan algunos resultados de -completitud del cálculo de ruta bajo varias restricciones aditivas / multiplicativas. El primer...
Problema: Dado representado por un circuito booleano, genera una uniformemente aleatoria tal que (o salida si no existe tal ). ϕ : { 0 , 1 }norte→ { 0 , 1 }ϕ:{0 0,1}norte→{0 0,1}\phi : \{0,1\}^n \to \{0,1\}x ∈ { 0 , 1 }norteX∈{0 0,1}nortex \in \{0,1\}^nϕ ( x ) =
¿Hay alguna forma de codificar una instancia de Subset Sum o el problema de partición numérica para que una solución (pequeña) a una relación entera produzca una respuesta? Si no es definitivamente, ¿en algún sentido probabilístico? Sé que LLL (y quizás PSLQ) se han utilizado con éxito moderado en...
Como todos saben, SAT está completo para wrt polinomial-tiempo muchas reducciones de uno. Todavía está completo wrt reducciones muchos-uno.N PnortePAG\mathsf{NP}A C0 0UNC0 0\mathsf{AC^0} Mi pregunta es ¿cuál es la profundidad mínima requerida para las reducciones? Más formalmente, ¿Cuál es la...
Me parece que la mayoría de los teóricos de la complejidad generalmente creen en la siguiente regla filosófica: Si no podemos imaginar un algoritmo eficiente para el problema , y podemos reducir el problema Una de problema B , entonces probablemente no es un algoritmo eficiente para el problema...
Cuando queremos demostrar que un L∈NPL∈NPL\in \bf NP es -Complete, entonces el enfoque estándar es exhibir un polinomio tiempo computable reducción de muchos uno de una conocida problema -Complete a . En este contexto, no necesitamos un límite estricto en el tiempo de ejecución de la reducción. Es...
Lance Fortnow afirmó recientemente que probar L! = NP debería ser más fácil que probar P! = NP : Separar NP del espacio logarítmico. Di cuatro enfoques en una encuesta previa al blog de 2001 sobre la diagonalización (Sección 3), aunque ninguno ha funcionado. Debería ser mucho más fácil que...
¿Puede todo lo siguiente sostenerse simultáneamente? LsLsL_s está contenido en para todos los enteros positivos .Ls+1Ls+1L_{s+1}sss L=⋃sLsL=⋃sLsL = \bigcup_s L_s es el lenguaje de todas las palabras finitas sobre .{0,1}{0,1}\{0,1\} Hay una cierta clase de complejidad y una noción de reducción...
Hace algún tiempo, publiqué una solicitud de referencia para problemas de gráficos en los que queremos encontrar una partición de 2 de los bordes donde ambos conjuntos cumplen una propiedad no relacionada con su cardinalidad. Estaba tratando de demostrar que el siguiente problema es NP-hard:...
La semana pasada, estaba leyendo de nuevo el trasncrito de Leslie en Lamport de 1982 de una conferencia que dio sobre Problemas resueltos, Problemas no resueltos y No problemas en concurrencia . El documento es fácilmente legible, pero una de las cosas que me hizo pensar es la siguiente...
La complejidad de clase PPAD fue inventado por Christos Papadimitriou en su seminal 1994 de papel . La clase está diseñada para capturar la complejidad de los problemas de búsqueda en los que la existencia de una solución está garantizada por el "argumento de paridad en gráficos dirigidos": si hay...
'Dado , ¿hay x , y ∈ N , a x 2 + b y = c ' es N P -completo?a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb Nax2+by=cax2+by=cax^2+by=cNPNP\mathsf{NP} ¿A qué clase de complejidad pertenece 'Dado , a qué pertenece x , y ∈ N , a x 2 + b y 2 = c '?a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb...
Este documento demuestra que en un juego con puertas y placas de presión, es difícil para PSPACE determinar si el avatar (del jugador) puede o no alcanzar una ubicación determinada. Esto se demuestra mediante una reducción de TQBF , y la longitud de las soluciones resultantes depende...
El SAT único es el problema bien conocido: dada una fórmula CNF , ¿es cierto que F tiene exactamente un modelo?FFFFFF Estoy interesado en el problema «Exactamente -SAT»: dada una fórmula F de CNF y un entero m > 1 , ¿es cierto que F tiene exactamente m modelos?mmmFFFm>1m>1m>1FFFmmm Ambos...
¿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...
Esta pregunta puede no ser técnica. Como hablante no nativo y TA para la clase de algoritmo, siempre me pregunté qué significa gadget en 'gadget de cláusula' o 'gadget variable'. El diccionario dice que un gadget es una máquina o un dispositivo, pero no estoy seguro de qué significado coloquial...
En la complejidad parametrizada, las personas utilizan la reducción de parámetros fijos manejables (FPT) para demostrar la dureza W [t]. Teóricamente, una reducción de FPT no es una reducción de tiempo polinomial, ya que puede ejecutarse exponencialmente en el parámetro k. Pero en la práctica,...
¿Existe un resultado conocido en la clase de complejidad 1-en-3-SAT con un número restringido de ocurrencias variables? Se me ocurrió la siguiente reducción parsimoniosa con Peter Nightingale, pero quiero citar algo si esto se sabe. Aquí está el truco que se nos ocurrió. Esto muestra que...
Me pregunto si las clases de NPC definidas por muchas reducciones y las reducciones de Turing son iguales. Editar: Otra pregunta, ¿las reducciones de Turing solo están colapsando las clases C y co-C para algunos C o hay una clase , ya que existe un problema que no está en bajo la reducción de Karp...