Encontrar una subsecuencia (de una secuencia muy larga) que no sume un número par

Question

[ Editado. He revisado el problema para centrarme en el caso especial de los enteros módulo 2].

Se le da una función f a partir de cadenas binarias x  ∈ {0,1} n a los enteros, o (sin pérdida de generalidad) sólo a {0,1}. Sólo se le promete que f no es del todo un número par.

Pregunta. Con sólo poly( n ) bits aleatorios, ¿cómo se describe un subconjunto S  ⊂ {0,1} n de modo que, con una probabilidad de al menos 1/poly( n ), la suma (módulo p ) de f ( x ) sobre todo x  ∈  S es impar?

Me interesan los algoritmos eficientes; por ejemplo, la búsqueda de un x  ∈ {0,1} n para lo cual f ( x ) es impar, al evaluar la mayoría de los valores de x no está permitido (ya que en el peor de los casos se tarda un tiempo exponencial).

Answer 1

A pesar de mi ingenuo escepticismo expresado en mi comentario, resulta que esto es posible: la prueba del Teorema de Valiant-Vazirani da tal $S$ .

• Como paso previo, adivinar el tamaño de $\{ x \colon f(x) \text{ is odd} \}$ hasta un factor de 2: es decir, adivinar un $r$ tal que el tamaño de ese conjunto esté en la ventana $[2^{r-1}, 2^r)$ . Esta suposición es correcta con probabilidad $1/(n+1)$ .

• Escoge $S$ para ser un subcubo aleatorio de codimensión alrededor de $r$ . (La codimensión debe ser $r \pm$ una constante absoluta. No conozco los detalles; actualizaré mi respuesta más tarde para precisarlo). Entonces, condicionado a que nuestra primera suposición sea correcta, con una probabilidad constante, se puede demostrar que hay exactamente una $x \in S$ tal que $f(x)$ es impar.

Así, $\sum \limits_{x \in S} f(x)$ es impar con probabilidad $\Omega (\frac{1}{n})$ . Hecho. (La descripción de $S$ toma $O(n)$ bits aleatorios).