Search

We study the complexity of a class of Markov decision processes and, more generally, stochastic games, called 1-exit Recursive Markov Decision Processes (1-RMDPs) and 1-exit Recursive Simple Stochastic Games (1-RSSGs), with strictly positive rewards. These are a class of finitely presented countable-state zero-sum turn-based stochastic games that subsume standard finite-state MDPs and Condon's simple stochastic games. They correspond to optimization and game versions of several classic stochastic models, with rewards. In particular, they correspond to the MDP and game versions of multi-type branching processes and stochastic context-free grammars with strictly positive rewards. The goal of the two players in the game is to maximize/minimize the total expected reward generated by a play of the game. Such stochastic models arise naturally as models of probabilistic procedural programs with recursion, and the problems we address are motivated by the goal of analyzing the optimal/pessimal expected running time in such a setting. We first show that in such games both players have optimal deterministic “stackless and memoryless” optimal strategies. We then provide polynomial-time algorithms for computing the exact optimal expected reward (which may be infinite, but is otherwise rational), and optimal strategies, for both the maximizing and minimizing single-player versions of the game, i.e., for (1-exit) Recursive Markov Decision Processes (1-RMDPs). It follows that the quantitative decision problem for positive reward 1-RSSGs is in NP ∩ coNP. We show that Condon's well-known quantitative termination problem for finite-state simple stochastic games (SSGs) which she showed to be in NP ∩ coNP reduces to a special case of the reward problem for 1-RSSGs, namely, deciding whether the value is ∞. By contrast, for finite-state SSGs with strictly positive rewards, deciding if this expected reward value is ∞ is solvable in P-time. We also show that there is a simultaneous strategy improvement algorithm that converges in a finite number of steps to the value and optimal strategies of a 1-RSSG with positive rewards.

We give polynomial time algorithms for quantitative (and qualitative) reachability analysis for Branching Markov Decision Processes (BMDPs). Specifically, given a BMDP, and given an initial population, where the objective of the controller is to maximize (or minimize) the probability of eventually reaching a population that contains an object of a desired (or undesired) type, we give algorithms for approximating the supremum (infimum) reachability probability, within desired precision ϵ > 0 , in time polynomial in the encoding size of the BMDP and in log ⁡ ( 1 / ϵ ) . We furthermore give P-time algorithms for computing ϵ-optimal strategies for both maximization and minimization of reachability probabilities. We also give P-time algorithms for all associated qualitative analysis problems, namely: deciding whether the optimal (supremum or infimum) reachability probabilities are 0 or 1. Prior to this paper, approximation of optimal reachability probabilities for BMDPs was not even known to be decidable. Our algorithms exploit the following basic fact: we show that for any BMDP, its maximum (minimum) non-reachability probabilities are given by the greatest fixed point (GFP) solution g ⁎ ∈ [ 0 , 1 ] n of a corresponding monotone max (min) Probabilistic Polynomial System of equations (max/minPPS), x = P ( x ) , which are the Bellman optimality equations for a BMDP with non-reachability objectives. We show how to compute the GFP of max/minPPSs to desired precision in P-time. We also study more general branching simple stochastic games (BSSGs) with (non-)reachability objectives. We show that: (1) the value of these games is captured by the GFP, g ⁎ , of a corresponding max-minPPS, x = P ( x ) ; (2) the quantitative problem of approximating the value is in TFNP; and (3) the qualitative problems associated with the value are all solvable in P-time.

Motivated by the recent cyber attack on the Ukrainian power grid, we study cyber attacks on power grids that affect both the physical infrastructure and the data at the control center–which therefore are cyber-physical in nature. In particular, we assume that an adversary attacks an area by: (i) remotely disconnecting some lines within the attacked area, and (ii) modifying the information received from the attacked area to mask the line failures and hide the attacked area from the control center. For the latter, we consider two types of attacks: (i) data distortion: which distorts the data by adding powerful noise to the actual data, and (ii) data replay: which replays a locally consistent old data instead of the actual data. We use the DC power flow model and prove that the problem of finding the set of line failures given the phase angles of the nodes outside of the attacked area is strongly NP-hard, even when the attacked area is known. However, we introduce the polynomial time REcurrent Attack Containment and deTection (REACT) Algorithm to approximately detect the attacked area and line failures after a cyber-physical attack. We numerically show that it performs well in detecting the attacked area, and detecting single, double, and triple line failures in small and large attacked areas.

We introduce and study the doubly balanced connected graph partitioning problem: Let G =( V , E ) be a connected graph with a weight (supply/demand) function p : V → {−1, +1} satisfying p ( V )=∑ j &isin V p ( j ) = 0. The objective is to partition G into ( V 1 , V 2 ) such that G [ V 1 ] and G [ V 2 ] are connected, ∣ p ( V 1 )∣,∣ p ( V 2 )∣≤ c p , and max{ ∣ V 1 / V 2 ∣,∣ V 2 / V 1 ∣} ≤ c s , for some constants c p and c s . When G is 2-connected, we show that a solution with c p =1 and c s =2 always exists and can be found in randomized polynomial time. Moreover, when G is 3-connected, we show that there is always a “perfect” solution (a partition with p ( V 1 )= p ( V 2 )=0 and ∣ V 1 ∣=∣ V 2 ∣, if ∣ V ∣≡ 0 (mod 4)), and it can be found in randomized polynomial time. Our techniques can be extended, with similar results, to the case in which the weights are arbitrary (not necessarily ±1), and to the case that p ( V )≠ 0 and the excess supply/demand should be split evenly. They also apply to the problem of partitioning a graph with two types of nodes into two large connected subgraphs that preserve approximately the proportion of the two types.

The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently, via arithmetic circuits using only multiplication and division gates, and integer inputs. Input instance: Four lists of positive integers: a 1,..., an ∈N+ n ; b 1,..., bn ∈N+ n ; c 1,..., cm ∈N+ m ; d 1, ..., dm ∈N+ m ; where each of the integers is represented in binary. Problem 1 (equality testing): Decide whether a 1 b 1 a 2 b 2⋯ anbn = c 1 d 1 c 2 d 2⋯ cmdm . Problem 2 (inequality testing): Decide whether a 1 b 1 a 2 b 2⋯ anbn ≥ c 1 d 1 c 2 d 2⋯ cmdm . Problem 1 is easily decidable in polynomial time using a simple iterative algorithm. Problem 2 is much harder. We observe that the complexity of Problem 2 is intimately connected to deep conjectures and results in number theory. In particular, if a refined form of the ABC conjecture formulated by Baker in 1998 holds, or if the older Lang-Waldschmidt conjecture (formulated in 1978) on linear forms in logarithms holds, then Problem 2 is decidable in P-time (in the standard Turing model of computation). Moreover, it follows from the best available quantitative bounds on linear forms in logarithms, namely, by Baker and Wüstholz [1993] or Matveev [2000], that if m and n are fixed universal constants then Problem 2 is decidable in P-time (without relying on any conjectures). This latter fact was observed earlier by Shub [1993]. We describe one application: P-time maximum probability parsing for arbitrary stochastic context-free grammars (where ε -rules are allowed).

We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We then prove that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and non-monotone utilities. Building on this result, we settle the long-standing open problem regarding the computation of an approximate Arrow-Debreu market equilibrium in markets with CES utility functions, by proving that it is PPAD-complete when the Constant Elasticity of Substitution parameter ρ is any constant less than − 1.

Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov chains. It is not known whether these problems can be solved in polynomial time. There are certain common computational principles underlying different types of equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP. Representative complete problems for these classes are respectively, pure Nash equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria in 2-player normal form games, and (mixed) Nash equilibria in normal form games with 3 (or more) players. This paper reviews the underlying computational principles and the corresponding classes.

We present algorithms for the qualitative and quantitative model checking of linear temporal logic (LTL) properties for recursive Markov chains (RMCs). Recursive Markov chains are a natural abstract model of procedural probabilistic programs and related systems involving recursion and probability. For the qualitative problem ("given a RMC A and an LTL formula /spl phi/, do the computations of A satisfy /spl phi/ almost surely?) we present an algorithm that runs in polynomial space in A and exponential time in /spl phi/. For several classes of RMCs, including RMCs with one exit (a special case that corresponds to well-studied probabilistic systems, e.g., multi-type branching processes and stochastic context-free grammars) the algorithm runs in polynomial time in A and exponential time in /spl phi/. On the other hand, we also prove that the problem is EXPTIME-hard, and hence it is EXPTlME-complete. For the quantitative problem ("does the probability that a computation of A satisfies /spl phi/ exceed a given threshold p?", or approximate the probability within a desired precision) we present an algorithm that runs in polynomial space in A and exponential space in /spl phi/. For linearly-recursive RMCs, we can compute the exact probability in time polynomial in A and exponential in /spl phi/. These results improve by one exponential, in both the qualitative and quantitative case, the complexity that one would obtain if one first translated the LTL formula to a Buchi automaton and then applied the model checking algorithm for Buchi automata from K. Etessami and M. Yannakakis (2005). Our results combine techniques developed in A. Pnueli and L. D. Zuck. (1993) for analysts of RMCs and in C. Courcoubetis and M. Yannakakis (1995) for LTL model checking of flat Markov Chains, and extend them with new techniques.

Suppose that we wish to transmit many messages from a node of a network to another, and the delays of the edges of the network are known. Once a message has been sent along an edge, the edge cannot be used to transmit another message until the first message arrives at the other end. We wish to estimate the throughput of such a network, that is, the number of messages from the source to the destination that can be transmitted within a given time T. We show that this throughput is hard to compute for finite values of T, but can be estimated asymptotically using flow techniques.

We analyze the problem of determining freedom from deadlock of transactions which control concurrency by locking in a distributed database. We use a graph-theoretic formalization of the problem and show that it is NP-hard even for two transactions. The problem of determining safety (serializability of all schedules) and deadlock freedom is also examined. We show that this problem can be solved in polynomial time for any fixed number of transactions.

We study several versions of the shortest-path problem when the map is not known in advance, but is specified dynamically. We are seeking dynamic decision rules that optimize the worst-case ratio of the distance covered to the length of the (statically) optimal path. We describe optimal decision rules for two cases: layered graphs of width two, and two-dimensional scenes with unit square obstacles. The optimal rules turn out to be intuitive, common-sense heuristics. For slightly more general graphs and scenes, we show that no bounded ratio is possible. We also show that the computational problem of devising a strategy that achieves a given worst-case ratio to the optimum path in a graph with unknown parameters is a universal two-person game, and thus PSPACE-complete, whereas optimizing the expected ratio is #P-hard.

A precise topological characterization of classes of graphs generated by certain context free graph grammars (CFGG) is given. An informal interpretation of the results is that CFGG cannot generate any interesting classes of graphs besides trees and series-parallel networks, except in trivial ways (e.g. by including subgraphs of higher connectivity explicitly in the production rules).

We investigate the complexity of finding locally optimal solutions to NP-hard combinatorial optimization problems. Local optimality arises in the context of local search algorithms, which try to find improved solutions by considering perturbations of the current solution (“neighbors” of that solution). If no neighboring solution is better than the current solution, it is locally optimal. Finding locally optimal solutions is presumably easier than finding optimal solutions. Nevertheless, many popular local search algorithms are based on neighborhood structures for which locally optimal solutions are not known to be computable in polynomial time, either by using the local search algorithms themselves or by taking some indirect route. We define a natural class PLS consisting essentially of those local search problems for which local optimality can be verified in polynomial time, and show that there are complete problems for this class. In particular, finding a partition of a graph that is locally optimal with respect to the well-known Kernighan-Lin algorithm for graph partitioning is PLS-complete, and hence can be accomplished in polynomial time only if local optima can be found in polynomial time for all local search problems in PLS.

We show that certain monotonic polynomial time queries are not expressible in variants of Datalog. The proof techniques include lower bounds for monotone circuit size and a "Pumping Lemma" for Datalog queries.