Qual é a complexidade deste jogo?

Esta é uma generalização da minha pergunta anterior .

Deixe ser uma máquina determinística em tempo polinomial que podem fazer perguntas para algum oráculo . Inicialmente está vazio, mas isso pode ser alterado após um jogo que será descrito abaixo. Seja uma string. $M$ $A$ $A$ $x$

Considere o seguinte jogo de Alice e Bob. Inicialmente, Alice e Bob têm e dólares, respectivamente. Alice quer e Bob quer . $m_A$ $m_B$ $M^A(x)=1$ $M^A(x)=0$

Em cada etapa do jogo, um jogador pode adicionar uma corda a ; isso custa dólar, onde é uma função computável em tempo polinomial. Além disso, um jogador pode perder o seu passo. $y$ $A$ $f(y)$ $f: \{0,1\}^* \to \mathbb{N}$

A jogada termina se ambos os jogadores gastarem todo o dinheiro ou se algum jogador errar um passo quando ele ou ela estiver em uma posição perdida (que é definida pelo valor atual de ). $M^A(x)$

Pergunta: é o problema de definir o vencedor deste jogo, dado que é um $M, f, x, m_A, m_B$

EXPSPACE - tarefa concluída?

Note-se que pode pedir (por pertencer a ) apenas strings de comprimento polinomial por isso não há sentido para Alice ou Bob para adicionar cordas mais longas para . Portanto, esse problema está no EXPSPACE . $M$ $A$ $A$

Na minha pergunta anterior, adicionar cada corda a custa um dólar (ou seja, ). Então (como foi mostrado por Lance Fortnow ), este jogo pertence ao EXPH e até ao PSPACE se . $A$ $f \equiv 1$ $m_A = m_B$

cc.complexity-theory complexity-classes gt.game-theory Alexey Milovanov
fonte

Você pode explicar por que você fez essa alteração no problema? Alice pode verificar se ela pode pagar por todas as seqüências de caracteres em (conforme definido na resposta de Lance para seu outro problema) em tempo polinomial. Como isso não resolve imediatamente o problema?

S

$S$

Stella Biderman

@StellaBiderman Alice realmente pode verificar isso em tempo polinomial. No entanto, se ela não tiver dinheiro suficiente, agora isso não significa que ela possa executar apenas etapas polinomiais (como ocorreu no jogo anterior).

Alexey Milovanov

Se ela não puder pagar por , ela pode vencer um oponente que sempre pula o turno deles? Talvez haja algo sobre a configuração do jogo que eu não esteja entendendo.

S

$S$

Stella Biderman

@ Stella Sim, porque podem ser outros caminhos aceitáveis. Por exemplo, suponha que , então pare e aceite. Nesse caso, . Mas se , então pode consultar e aceitar se . Nesse caso, é suficiente se Alice tiver spondulix suficiente para .

x_{1} \in A

$x_1\in A$

M

$M$

S = {x_{1}}

$S=\{x_1\}$

x_{1} \notin A

$x_1\notin A$

M

$M$

x_{2}

$x_2$

x_{2} \in A

$x_2\in A$

x_{2}

$x_2$

Domotorp 27/10/19

Respostas:

Isso deve ser completo no EXPSPACE. Esboçarei como obter um número exponencial de alternâncias, sem reduzir nenhum problema completo do EXPSPACE a este, mas a partir daqui deve ser simples concluir.

Denuncie as palavras no oráculo após arredondadas por , então inicialmente . Indique as palavras consultadas por por . A principal observação é que quem está perdendo com , pode-se supor para adicionar algo de para . Isso ocorre porque neste jogo cada movimento custa dinheiro, queremos mover o mínimo possível; não faz sentido agir até estarmos ganhando. Mas isso também implica que, se estamos perdendo, não faz sentido adicionar algo de fora de . $t$ $A_t$ $A_0=\emptyset$ $M^{A_t}$ $Q_t$ $A_t$ $Q_t$ $A$ $Q_t$

Assuma por simplicidade que $M$ é executado por exatamente $2n$ passos e em etapas $2i$ e $2i+1$ ele consulta uma palavra de comprimento exatamente $i$ . A função de custo $f$ será simplesmente $2^{-i}$ em palavras de comprimento $i$ . O jogo será tal que Alice sempre precisa adicionar palavras comprimento ímpar e Bob sempre precisa adicionar palavras de comprimento até mesmo para $A$ . Suponha que seja ímpar e inicialmente Alice esteja perdendo. $n$

Os orçamentos $m_A$ e $m_B$ será ajustada de modo que ela pode escolher exactamente um do comprimento $n$ seja consultada por $M^{A_0}$ para ser adicionado a $A$ . O jogo será tal que isso fará dela a vencedora, então Bob terá que se mudar. Mais uma vez, devido a restrições de orçamento, ele terá que escolher exatamente um do comprimento $n-1$ palavras consultados pela $M^{A_1}$ para ser adicionado a $A$ . Após a adição de qualquer uma dessas opções, $M^{A_2}$ consultará duas novas palavras $n$ comprimento (as mesmas, independentemente da palavra em que Bob adicionou $A$ ) e Bob vencerá. Alice será forçada a adicionar exatamente uma dessas novaspalavras $n$ em $A$ para fazê-la vencer.

O jogo continua desta maneira, que pode ser imaginado como seguindo os galhos de uma árvore binária completa de profundidade $n$ , embora em cada nó de ramificação um dos jogadores (determinado que pela paridade da profundidade do nó) precise fazer uma escolha sobre qual palavra para adicionar ao $A$ . Depois de passarem pela árvore, ficarão sem seu orçamento. Se, em qualquer estágio do jogo, um deles decidir adicionar alguma palavra mais curta (por exemplo, Alice, um comprimento $k<n$ palavra de $Q_0$ na primeira etapa), se o outro jogador (no nosso exemplo, Bob) jogar sempre a palavra mais longa que puder na árvore binária, ele terá algum dinheiro sobrando no final e faremos o jogo para que ele possa usar isso ganhar. (Observe que Alice também pode ter algum dinheiro sobrando, mas Bob terá mais, então projetamos o jogo final que, se um deles tiver mais dinheiro, esse jogador poderá ganhar.)

$A$

domotorp
fonte

Obrigado pela sua resposta. Fiz algumas perguntas por e-mail.

Alexey Milovanov