Un problema de partición con restricciones de orden

En el OrderedPartitionproblema, la entrada es dos secuencias de enteros positivos, y . El resultado es una partición de los índices en dos subconjuntos disjuntos, y , de modo que:$n$$(a_i)_{i\in [n]}$$(b_i)_{i\in [n]}$$[n]$$I$$J$

1. $\sum_{i\in I} a_i = \sum_{j\in J} a_i$
2. Para todo y para todo : .$i\in I$$j\in J$$b_i\leq b_j$

En otras palabras, primero tenemos que ordenar los índices en una línea para que aumente débilmente, y luego cortar la línea para que la suma de en ambos lados sea la misma.$b_i$$a_i$

Si todos son iguales, entonces la condición 2 es irrelevante y tenemos una instancia del problema NP-hard . Por otro lado, si todos los son diferentes, entonces la condición 2 impone un orden único en los índices, por lo que solo hay opciones para verificar y el problema se vuelve polinómico. ¿Qué sucede entre estos casos?$b_i$Partition$b_i$$n-1$

Para formalizar la pregunta, defina por OrderedPartition[n,d], para , el problema restringido a instancias de tamaño , en el que el subconjunto más grande de -s idénticas es de tamaño . Entonces, el caso fácil, cuando todos los -s son diferentes, es , y el caso difícil, cuando todos los b i -s son idénticos, es .$1\leq d\leq n$$n$$b_i$$d$$b_i$OrderedPartition[n,1]$b_i$OrderedPartition[n,n]

Más en general, para cualquier $n$ y $d$ , en cualquier OrderedPartition[n,d]caso, el número de posibles particiones condición 2 respetando es $O(n 2^d)$ . Por lo tanto, si $d\in O(\log{n})$ , entonces OrderedPartition[n,d]todavía es polinomial en $n$ .

Por otra parte, para cualquier $n$ y $d$ , podemos reducir de un Partitionproblema $d$ enteros a OrderedPartition[n,d]. Sea $p_1,\ldots,p_d$ una instancia de Partition. Definir una instancia de OrderedPartition[n,d]por:

• Para cada $i\in \{1,\ldots,d\}$ , deje $a_i := 2n\cdot p_i$ y $b_i := 1$ .
• Para cada $i\in \{d+1,\ldots,n\}$ , deje $a_i := 1$ y $b_i := i$
  _{[si $n-d$ es impar, haga $a_n:=2$ modo que la suma sea par]} .

Por lo tanto, si $d\in\Omega(n^{1/k})$ , para cualquier número entero $k\geq 1$ , entonces OrderedPartition[n,d]es NP-hard.

PREGUNTA: ¿Qué sucede en los casos intermedios, en los que $d$ es superlogarítmico pero subpolinomial en $n$ ?

Intuitivamente, los casos intermedios no deben ser ni en P ni NP-hard. Quizás depende exactamente de lo que entendemos por "caso intermedio". Aquí hay una interpretación para la cual podemos probar algo.

Nota: La hipótesis del tiempo exponencial , o ETH, es que no es el caso de que, para cada constante $\epsilon>0$ , SAT tenga un algoritmo que se ejecuta en el tiempo $2^{n^{\epsilon}}$ . Vea también esta discusión sobre cs.stackexchange. Hasta donde sabemos, ETH es cierto.

Defina OP c como la restricción del problema OrderedPartition a instancias donde d ≤ log c n . De manera equivalente, a instancias donde n ≥ 2 d 1 / c . Aquí pretendemos que OP c capture lo que la publicación quiere decir con "instancias intermedias". Mostramos que no es probable que estas instancias estén en P ni en NP-hard.$_c$$d \le \log^c n$$n \ge 2^{d^{1/c}}$$_c$

Lema 1. Si OP c está en P para todo c , entonces ETH falla.$_c$$c$

Prueba. Suponga que OP c está en P para todos los c . Es decir, para alguna función f , OP c tiene un algoritmo que se ejecuta en el tiempo n f ( c ) . Las entradas SAT de tamaño n se reducen (a través de la Partición como se describe en la publicación) a OrderedPartition [ 2 n b / c , n b ] , para alguna constante b y cualquier constante c > 0 . Entonces, las entradas SAT de tamaño n se reducen a OP c instancias de tamaño 2 n$_c$$c$$f$$_c$$n^{f(c)}$$n$$[2^{n^{b/c}}, n^b]$$b$$c>0$$n$$_c$$2^{n^{b/c}}$ , que puede resolverse en el tiempo$2^{f(c)n^{b/c}}$ mediante el algoritmo para OPc. Para cualquierϵ>0, tomando, por ejemplo,c=2b/ϵ, SAT puede resolverse en el tiempo2 c ′ n ϵ / 2 ≤2 n ϵ (parangrande), violando ETH. ◻$_c$$\epsilon>0$$c=2b/\epsilon$$2^{c' n^{\epsilon/2}} \le 2^{n^{\epsilon}}$$n$$~~~~\Box$

Nota: Me parece probable que incluso OP 2 no esté en P, pero mostrar algo así sería similar a mostrar, por ejemplo, que SAT no tiene ningún algoritmo ejecutándose en el tiempo 2 √$_2$$2^{\sqrt n}$ .

Lema 2. Si OP c es NP-hard para alguna c , entonces ETH falla.$_c$$c$

Prueba. Supongamos que OP c es NP-hard para algunos c . Luego, las entradas SAT de tamaño n se reducen a OP c en el tiempo O ( n b ) para algunos b . Es decir, a instancias de OrdereredPartition [ n b , d ] donde d ≤ log c ( n b ) . Como se observó en la publicación, tales instancias pueden resolverse en el tiempo n O ( 1 ) 2 d = n O ( 1$_c$$c$$n$$_c$$O(n^b)$$b$$[n^b, d]$$d\le \log^c (n^b)$$n^{O(1)} 2^d = n^{O(1)} 2^{\log^c (n^b)}$ , (¡fuertemente!) Violando ETH. ◻$~~~~\Box$

Probablemente se pueda mostrar algo más limpio o más fuerte. Si tuviera que adivinar, definiría NP d ( n ) como la clase de complejidad compuesta por aquellos lenguajes que tienen un algoritmo de tiempo polivinílico no determinista que, en cualquier entrada de tamaño n , utiliza como máximo d ( n ) conjeturas no deterministas. (Aquí d podría ser cualquier función). Entonces OrderedPartition [ n , d ( n ) ] está en NP d ( n )$_{d(n)}$$n$$d(n)$$d$$[n, d(n)]$$_{d(n)}$. ¿Quizás está completo para esa clase bajo reducciones de poli-tiempo? Una suposición natural para un problema que debería estar completo para la clase sería: dado un circuito de tamaño $n$ con $d$ puertas de entrada, ¿hay alguna entrada que haga que la salida del circuito sea Verdadera? O algo así. (Me pregunto cómo se compara esto con, digamos, definir SAT p ( n ) para que consista en instancias SAT, rellenadas con p ( n ) bits inútiles para agrandar la entrada. Cuando p ( n ) es superpolinomial pero sub-exponencial, el problema no debe ser NP-hard ni en P.)$_{p(n)}$$p(n)$$p(n)$

ps Véase también Consecuencias de pruebas / algoritmos sub-exponenciales para SAT .