Hasta qué punto, la capacidad computacional para tareas difíciles ayuda a resolver tareas fáciles

En resumen, la pregunta es: en qué medida, la capacidad computacional para tareas difíciles realmente lo ayuda a resolver tareas fáciles. (Podría haber varias formas de hacer esta pregunta interesante y no trivial, y aquí hay uno de esos intentos).

Pregunta 1:

Considere un circuito para resolver SAT para una fórmula con n variables. (O para encontrar el ciclo hamiltoniano para un gráfico con aristas).$n$

Suponga que cada puerta permite el cálculo de una función booleana arbitraria en variables. Para concreción tomemos m = 0.6 n .$m$$m=0.6 n$

La hipótesis del tiempo exponencial fuerte (SETH) afirma que incluso con puertas tan fuertes necesitamos un tamaño de circuito superpolinomial. De hecho, necesitamos un tamaño de al menos por cada ϵ . En cierto sentido, las compuertas en la fracción de las variables que representan funciones booleanas muy complicadas (mucho más allá de la completitud NP) no le brindan mucha ventaja.$\Omega (2^{(0.4-\epsilon) n})$$\epsilon.$

Además podemos preguntar:

(i) ¿Podemos tener dicho circuito de tamaño ? 2 ( 1 - ϵ ) n ?$2^{0.9 n}$$2^{(1-\epsilon)n}$

Una respuesta "no" será un vasto fortalecimiento del SETH. Por supuesto, tal vez haya una respuesta fácil de "Sí", que simplemente echo de menos.

(ii) Si la respuesta a (i) es SÍ, las puertas que calculan funciones booleanas arbitrarias ofrecen algunas ventajas en comparación con las puertas que "simplemente" calculan (digamos) funciones NP arbitrarias; o simplemente instancias más pequeñas de SAT en sí?

La siguiente pregunta intentos para pedir algo similar para las preguntas en .$P$

Pregunta 2:

$m< n$$m=0.6n$$m$$m=n^\alpha$

$m$

$m$$m$

$m$$m^d$$d$

d) En un solo paso puede realizar puertas booleanas ordinarias.

$n$

(Esto puede estar relacionado con problemas bien conocidos sobre cómputo paralelo o sobre oráculos).

$2^{2^m \cdot s}$$s$$s=2^{n-m}$