Reductions to sets of low information content (2009)
Arvind, Vikraman, Han, Y., Hamachandra, L., Köbler, Johannes, Lozano, A., Mundhenk, Martin, ...
This paper is concerned with three basic questions about sparse sets: (1) With respect to what types of reductions might NP have hard or complete sparse sets? (2) If a set A reduces to a sparse set,...
On bounded truth-table, conjunctive, and randomized reductions to sparse sets (2009)
Arvind, Vikraman, Köbler, Johannes, Mundhenk, Martin
In this paper we study the consequences of the existence of sparse hard sets for different complexity classes under certain types of deterministic, randomized and nondeterministic reductions. We show...
Lowness and the complexity of sparse and tally descriptions (2009)
Arvind, Vikraman, Köbler, Johannes, Mundhenk, Martin
We investigate the complexity of obtaining sparse descriptions for sets in various reduction classes to sparse sets. Let A be a set in a certain reduction class R(SPARSE) to the class of sparse sets....
Reliable reductions, high sets and low sets (2009)
Arvind, Vikraman, Köbler, Johannes, Mundhenk, Martin
Measuring the information content of a set by the space-bounded Kolmogorov complexity of its characteristic sequence, we investigate the (non-uniform) complexity of sets A in EXPSPACE/poly that...
The Complexity of Satisfiability for Fragments of Hybrid Logic -- Part I (2009)
Meier, Arne, Mundhenk, Martin, Schneider, Thomas, Thomas, Michael, Weber, Volker, Weiss, Felix
The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this paper, we investigate...
Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor D
In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal...
Complexity of Hybrid Logics over Transitive Frames (2008)
Mundhenk, Martin, Schneider, Thomas, Schwentick, Thomas, Weber, Volker
This paper examines the complexity of hybrid logics over transitive frames, transitive trees, and linear frames. We show that satisfiability over transitive frames for the hybrid language extended...
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments (2008)
Bauland, Michael, Mundhenk, Martin, Schneider, Thomas, Schnoor, Henning, Schnoor, Ilka, Vollmer, Heribert
In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal...
Complexity of DNF and Isomorphism of Monotone Formulas (2008)
Judy Goldsmith, Matthias Hagen, Martin Mundhenk
Abstract. We investigate the complexity of finding prime implicants and minimal equivalent DNFs for Boolean formulas, and of testing equivalence and isomorphism of monotone formulas. For DNF related...
Judy Goldsmith, Martin Mundhenk
It is known that determinining whether a DEC-POMDP, namely, a cooperative partially observable stochastic game (POSG), has a cooperative strategy with positive expected reward is complete for NEXP....
Undecidability of Multi-modal Hybrid Logics ⋆ Abstract (2008)
Martin Mundhenk, Thomas Schneider
This paper establishes undecidability of satisfiability for multi-modal logic equipped with the hybrid binder ↓ , with respect to frame classes over which the same language with only one modality...
Judy Goldsmith, Martin Mundhenk
It is known that determinining whether a DEC-POMDP, namely, a cooperative partially observable stochastic game (POSG), has a cooperative strategy with positive expected reward is complete for NEXP....
Complexity of DNF and Isomorphism of Monotone Formulas (2008)
Judy Goldsmith, Matthias Hagen, Martin Mundhenk
Abstract. We investigate the complexity of finding prime implicants and minimal equivalent DNFs for Boolean formulas, and of testing equivalence and isomorphism of monotone formulas. For DNF related...
Judy Goldsmith, Matthew A. Levy, Martin Mundhenk
Amy tries the same approach, and her program works for small circuits. But, when she tries larger circuits, the program runs for ages! Her bosses are getting impatient, but no algorithm she can think...
Propositional Proofs and Their Complexity (2007)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Martin Mundhenk, Martin Mundhenk
Contents 1 Propositional Logic 2 1.1 Propositions and formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Boolean functions . . . . . . . . . . . . . . . . . . . . . . . ....
Good policies for partially-observable Markov decision processes are hard to find (2007)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena
Optimal policy computation in finite-horizon Markov decision processes is a classical problem in optimization with lots of pratical applications. For stationary policies and infinite horizon it is...
Nonapproximability Results for Partially Observable Markov Decision Processes (2007)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Christopher Lusena, Christopher Lusena, Judy Goldsmith, ...
Electronic copies of technical reports are available:
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender, Name Martin Mundhenk
and by the Deutsche Akademische Austauschdienst (DAAD) grant 315/PPP/gu-ab, and by NSF grants CCR-9315354, CCR-9610348, and CCR-9509603. Portions of this work were performed while at the Institute of...
The tractability of model-checking for LTL: The good, the bad, and the ugly fragments (2007)
Michael Baul, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
vollmerATthi.uni-hannover.de Abstract. In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete,...
The tractability of model-checking for LTL: The good, the bad, and the ugly fragments (2007)
Michael Baul, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer
Abstract. In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of...
The complexity of hybrid logics over equivalence relations (2007)
Martin Mundhenk, Thomas Schneider
This paper examines and classifies the computational complexity of model checking and satisfiability for hybrid logics over frames with equivalence relations. The considered languages contain all...
The complexity of hybrid logics over equivalence relations (2007)
Martin Mundhenk, Thomas Schneider
This paper examines and classifies the computational complexity of model checking and satisfiability for hybrid logics over frames with equivalence relations. The considered languages contain all...
The complexity of hybrid logics over equivalence relations (2007)
Martin Mundhenk, Thomas Schneider
This paper examines and classifies the computational complexity of model checking and satisfiability for hybrid logics over frames with equivalence relations. The considered languages contain all...
Undecidability of multi-modal hybrid logics (2006)
Martin Mundhenk, Thomas Schneider
This paper establishes undecidability of satisfiability for multi-modal logic equipped with the hybrid binder ↓ , with respect to frame classes over which the same language with only one modality...
Complexity of hybrid logics over transitive frames (2005)
Martin Mundhenk, Thomas Schneider, Thomas Schwentick, Volker Weber
Abstract. This paper examines the complexity of hybrid logics over transitive frames and transitive trees. We show that satisfiability over transitive frames for the hybrid language extended with ↓...
Complexity of Hybrid Logics over Transitive Frames (2005)
Martin Mundhenk, Thomas Schneider, Thomas Schwentick, Volker Weber
This paper examines the complexity of hybrid logics over transitive frames and transitive trees. We show that satisfiability over transitive frames for the hybrid language extended with is...
Complexity of hybrid logics over transitive frames (2005)
Martin Mundhenk, Thomas Schneider, Thomas Schwentick, Volker Weber
Abstract. This paper examines the complexity of hybrid logics over transitive frames and transitive trees. We show that satisfiability over transitive frames for the hybrid language extended with #...
Complexity of hybrid logics over transitive frames (2005)
Martin Mundhenk, Thomas Schneider, Thomas Schwentick, Volker Weber
Abstract. This paper examines the complexity of hybrid logics over transitive frames and transitive trees. We show that satisfiability over transitive frames for the hybrid language extended with ↓...
Nonapproximability results for partially observable Markov decision processes (2001)
Christopher Lusena, Judy Goldsmith, Martin Mundhenk
We show that for several variations of partially observable Markov decision processes, polynomial-time algorithms for finding control policies are unlikely to or simply don't have guarantees of...
Complexity of Finite-Horizon Markov Decision Process Problems (2000)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender, Name Martin Mundhenk, Name Judy Goldsmith
This paper considers the computational complexity of the basic tasks facing such a controller.
Instance complexity was introduced by Orponen, Ko, Schoning, and Watanabe [14] as a measure of the complexity of individual instances of a decision problem. Comparing instance complexity to...
Complexity of Finite-Horizon Markov Decision Process Problems (2000)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender, Name Judy Goldsmith
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specic permission...
The Complexity of Planning with Partially-Observable Markov Decision Processes (2000)
Contents 1 Introduction 1 2 Partially-Observable Markov Decision Processes 13 2.1 Policies and Performances . . . . . . . . . . . . . . . . . . . . 14 2.2 Examples . . . . . . . . . . . . . . . . . ....
Complexity of finite-horizon Markov decision process problems (2000)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
Instance Complexity of NP-hard sets (1999)
Instance complexity was introduced by Orponen, Ko, Schoning, and Watanabe [7, 14, 15] as a measure of the complexity of individual instances of a decision problem. Comparing instance complexity to...
The Complexity of Optimal Small Policies (1999)
Trierer Forschungsberichte, Fachbereich Iv, Martin Mundhenk, Martin Mundhenk
We investigate the complexity of problems concerned with partially-observable Markov decision processes which are run for a nite number of steps under small policies. The calculation of the expected...
Instance complexity was introduced by Orponen, Ko, Schoning, and Watanabe [14] as a measure of the complexity of individual instances of a decision problem. Comparing instance complexity to...
The Computational Complexity of Probabilistic Planning (1998)
Michael L. Littman, Judy Goldsmith, Martin Mundhenk
We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and...
Complexity Issues in Markov Decision Processes (1998)
Judy Goldsmith, Martin Mundhenk
We survey the complexity of computational problems about Markov decision processes: evaluating policies, finding good and best policies, approximating best policies, and related decision problems. 1...
Complexity issues in Markov decision processes (1998)
Judy Goldsmith, Martin Mundhenk
We survey the complexity of computational problems about Markov decision processes: evaluating policies, finding good and best policies, approximating best policies, and related decision problems. 1...
The computational complexity of probabilistic planning (1998)
Michael L. Littman, Judy Goldsmith, Martin Mundhenk
We examine the computational complexity of testing and nding small plans in probabilistic planning domains with both at and propositional representations. The complexity of plan evaluation and...
Martin Mundhenk, Judy Goldsmith, Eric Allender
A partially-observable Markov decision process (POMDP) is a generalization of a Markov decision process that allows for incomplete information regarding the state of the system. POMDPs are used to...
The Complexity of Plan Existence and Evaluation in Probabilistic Domains (1997)
Judy Goldsmith, Michael L. Littman, Martin Mundhenk
We examine the computational complexity of testing and finding small plans in probabilistic planning domains (both flat and succinct). We show that many problems of interest are complete for a...
The Complexity of Plan Existence and Evaluation in Probabilistic Domains (1997)
Judy Goldsmith Dept, Judy Goldsmith, Michael L. Littman, Martin Mundhenk, Fb Theoretische Informatik
We examine the computational complexity of testing and finding small plans in probabilistic planning domains with succinct representations. We find that many problems of interest are complete for a...
The Complexity of Plan Existence and Evaluation in Probabilistic Domains (1997)
Judy Goldsmith, Michael L. Littman, Martin Mundhenk, Fb Theoretische Informatik
We examine the computational complexity of testing and finding small plans in probabilistic planning domains with succinct representations. We find that many problems of interest are complete for a...
Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems (1997)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
The computational complexity of finite horizon policy evaluation and policy existence problems are studied for several policy types and representations of Markov decision processes. In almost all...
Good policies for partially-observable Markov decision processes are hard to find (1997)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena
Optimal policy computation in finite-horizon Markov decision processes is a classical problem in optimization with lots of pratical applications. For stationary policies and infinite horizon it is...
Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems (1997)
Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
The computational complexity of finite horizon policy evaluation and policy existence problems are studied for several policy types and representations of Markov decision processes. In almost all...
Encyclopaedia of Complexity Results for Finite-Horizon Markov Decision Process Problems (1997)
By Martin, Martin Mundhenk, Judy Goldsmith, Christopher Lusena, Eric Allender
The computational complexity of finite horizon policy evaluation and policy existence problems are studied for several policy types and representations of Markov decision processes. In almost all...
Martin Mundhenk, Judy Goldsmith, Eric Allender
A partially-observable Markov decision process (POMDP) is a generalization of a Markov decision process that allows for incomplete information regarding the state of the system. POMDPs are used to...
The Complexity of Deterministically Observable Finite-Horizon Markov Decision Processes (1996)
Judy Goldsmith, Chris Lusena, Martin Mundhenk
We consider the complexity of the decision problem for different types of partially-observable Markov decision processes (MDPs): given an MDP, does there exist a policy with performance ? 0? Lower...
The complexity of unobservable finite-horizon Markov decision processes (1996)
Martin Mundhenk, Judy Goldsmith, Eric Allender
Markov Decision Processes (MDPs) model controlled stochastic systems. Like Markov chains, an MDP consists of states and probabilistic transitions; unlike Markov chains, there is assumed to be an...
Judy Goldsmith, Matthew A. Levy, Martin Mundhenk
this paper. References
Judy Goldsmith, Matthew A. Levy, Martin Mundhenk
this paper. References
Monotonic Oracle Machines and Binary Search Reductions (1996)
Polynomial-time oracle machines being restricted to perform a certain search technique in the oracle are considered. These search techniques (e.g. binary search, prefix search) are expressed as...
Monotonous Oracle Machines (1995)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Martin Mundhenk, Martin Mundhenk
Polynomial-time oracle machines being restricted to perform a certain search technique in the oracle are considered. These search techniques (e.g. binary search, prefix search) are expressed as...
Monotonous Oracle Machines (1995)
Mathematik Informatik, Trierer Forschungsberichte, Fachbereich Iv, Martin Mundhenk, Martin Mundhenk
Polynomial-time oracle machines being restricted to perform a certain search technique in the oracle are considered. These search techniques (e.g. binary search, prefix search) are expressed as...
On Self-Reducible Sets of Low Information Content (1994)
Self-reducible sets have a rich internal structure. The information contained in these sets is encoded in some redundant way. Therefore a lot of the information of the set is easily accessible. In...
On bounded truth-table, conjunctive, and randomized reductions to sparse sets (1992)
Vikraman Arvind, Johannes Kobler, Martin Mundhenk, Oberer Eselsberg
In this paper we study the consequences of the existence of sparse hard sets for different complexity classes under certain types of deterministic, randomized and nondeterministic reductions. We show...
Bounded Truth-Table and Conjunctive Reductions to Sparse and Tally Sets (1992)
Johannes Köbler, Ulmer Informatik-berichte, Vikraman Arvind, Vikraman Arvind, Johannes Kobler, Martin Mundhenk, ...
In this paper we study the consequences of the existence of sparse hard sets for different complexity classes under certain types of deterministic, randomized and nondeterministic reductions. We show...
Random Languages for Non-Uniform Complexity Classes (1991)
Martin Mundhenk, Rainer Schuler
A language A is considered to be random for a class C if for every language B in C the fraction of the strings where A and B coincide is approximately 1/2. We show that there exist languages in...