Caracterización de máquina de

14

SUNCyo es la clase de problemas de decisión que puede resolver una familia de circuitos de profundidad con compuertas OR sin límites y con compuertas AND con límites. Las negaciones solo están permitidas en el nivel de entrada. Se sabe que S A C i para i 1 está cerrado bajo el complemento y S A C 0 no. Además, S A C 1 = L o g C F L ) espacio dependiente y tiempo polinómico limitado PDA auxiliar. ¿Hay caracterizaciones de máquinas similares deO(Iniciar sesiónyonorte)SUNCyoyo1SAC0SAC1=LogCFL y, por lo tanto, tiene una caracterización de máquina, ya que LogCFL es el conjunto de idiomas aceptados por un O(logn)SACi para ?i2

Shiva Kintali
fuente
¿Se supone que y yo somos lo mismo? kyo
András Salamon
Si. Lo siento por el error tipográfico. Lo arregló ahora.
Shiva Kintali

Respuestas:

14

Si. Alturas de pila. , es decir, con O ( log n ) espacio y O ( log n ) altura de pila; esto implica log n configuraciones y por lo tanto log 2 ( n )SUNC1=norteUNtuXPAGreUN(Iniciar sesiónnorte,Iniciar sesiónnorte)O(Iniciar sesiónnorte)O(Iniciar sesiónnorte)Iniciar sesiónnorteIniciar sesión2(norte) bits. Tenemos

SUNCk=norteUNtuXPAGreUN(Iniciar sesiónnorte,Iniciar sesiónknorte);

Estas máquinas se ejecutarán en el tiempo . Sin restricción de la altura de la chimenea, obtendremos exactamente P . El resultado debe ser de: W. Ruzzo, alternancia acotada del tamaño del árbol. JCSS 1980.2Iniciar sesiónk(norte)PAG

V Vinay
fuente
Vinay, puedes usar látex regular en la respuesta: podría ayudar a que sea un poco más legible
Suresh Venkat