Los juegos de preguntas y respuestas (Q/A games) son una generalización del juego de Ulam y modelan la extracción de información en paralelo. Un juego de preguntas y respuestas, G = (D,s,(q1,...,qr)), se juega en un gráfico acíclico dirigido, D = (V,E), con un vértice de inicio distinguido s, entre dos jugadores, Paul y Carole. En la i-ésima ronda, Paul selecciona un set, ¡Qi ! V , de como máximo vértices no terminales de qi. Carole responde eligiendo un borde saliente de cada vértice en Qi. Al final de r rondas, Paul gana si y solo si las respuestas de Carole definen un camino único desde la raíz hasta uno de los vértices terminales en D. Exploramos la complejidad de determinar si Carole gana un juego de preguntas y respuestas G. Mostramos que el problema es NP-duro si el juego está restringido a una pregunta por ronda, excepto en la última ronda. El problema sigue siendo NP-duro si restringimos el juego a dos rondas. La versión general del juego es PSPACE-completo.

Les jeux de questions/réponses (jeux Q/R) sont une généralisation du jeu d'Ulam et ils modélisent l'extraction d'informations en parallèle. Un jeu Q/A, G = (D,s,(q1,...,qr)), se joue sur un graphe acyclique dirigé, D = (V,E), avec un sommet de départ s distingué, entre deux joueurs, Paul et Carole. Au i-ème tour, Paul sélectionne un set, Qi ! V , d'au plus des sommets non terminaux qi. Carole répond en choisissant un bord sortant de chaque sommet de Qi. À la fin des rounds, Paul gagne si et seulement si les réponses de Carole définissent un chemin unique de la racine à l'un des sommets terminaux dans D. Nous explorons la complexité de déterminer si Carole gagne un jeu Q/R. Nous montrons que le problème est NP-difficile si le jeu est limité à une question par round, à l'exception du dernier round. Le problème reste NP-difficile si nous limitons le jeu à deux tours. La version générale du jeu est PSPACE-complet.

Question/Answer games (Q/A games) are a generalization of Ulam's game and they model information extraction in parallel. A Q/A game, G = (D,s,(q1,...,qr)), is played on a directed acyclic graph, D = (V,E), with a distinguished start vertex s, between two players, Paul and Carole. In the i-th round, Paul selects a set, Qi ! V , of at most qi non-terminal vertices. Carole responds by choosing an outgoing edge from each vertex in Qi. At the end of r rounds, Paul wins if and only if Carole's answers define a unique path from the root to one of the terminal vertices in D. We explore the complexity of determining if Carole wins a Q/A game G. We show that the problem is NP-hard if the game is restricted to one question per round, except for the last round. The problem remains NP-hard if we restrict the game to two rounds. The general version of the game is PSPACE-complete.

ألعاب الأسئلة والأجوبة (ألعاب الأسئلة والأجوبة) هي تعميم لعبة أولام وهي نموذج لاستخراج المعلومات بالتوازي. يتم لعب لعبة Q/A، G = (D،s، (q1،...، qr))، على رسم بياني دوري موجه، D = (V،E)، مع رأس بداية مميز، بين لاعبين، بول وكارول. في الجولة i - th، يختار بول مجموعة، Qi ! V ، من الرؤوس غير الطرفية qi على الأكثر. تستجيب كارول عن طريق اختيار حافة صادرة من كل رأس في Qi. في نهاية الجولات r، يفوز بول إذا وفقط إذا كانت إجابات كارول تحدد مسارًا فريدًا من الجذر إلى أحد القمم الطرفية في D. نستكشف تعقيد تحديد ما إذا كانت كارول تفوز في لعبة Q/A G. نظهر أن المشكلة صعبة إذا كانت اللعبة تقتصر على سؤال واحد في كل جولة، باستثناء الجولة الأخيرة. تبقى المشكلة NP - hard إذا قصرنا اللعبة على جولتين. النسخة العامة من اللعبة هي PSPACE - complete.