The classes of functions $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ that are analogous to the class $# P$ are defined. Functions in $# \textit{PSPACE}$ count the number of accepting computations of a ... bounded Turing machine, and functions in $\natural \textit{PSPACE}$ count the number of accepting computations of nondeterministic ... known about $# P$, exact characterizations of both $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ are found. In particular, $# PSPACE = FSPACE$ (the class of functions computable in polynomial ...
Tópico(s): Complexity and Algorithms in Graphs
1989 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
... on transition systems induced by OCA. A ${\mathsf{PSPACE}}$ upper bound is inherited from the modal $\mu$- ... fixed OCA, ${\mathsf{CTL}}$ model checking is ${\mathsf{PSPACE}}$-hard, i.e., expression complexity is ${\mathsf{PSPACE}}$-hard. Third, we show that there already exists ... for which model checking of OCA is ${\mathsf{PSPACE}}$-hard, i.e., data complexity is ${\mathsf{PSPACE}}$-hard as well. To obtain the latter result, ... logspace-uniform ${\mathsf{NC}}^1$ and (ii) ${\mathsf{PSPACE}}$ is $\mathsf{AC}^0$-serializable. We demonstrate that ...
Tópico(s): Logic, programming, and type systems
2013 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Robert A. Hearn, Erik D. Demaine,
... of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. ... to show that several motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to ... result that the restricted Rush HourTM puzzles are PSPACE-complete [Theoret. Comput. Sci. 270(1–2) (2002) ... We also greatly strengthen the conditions for the PSPACE-hardness of the Warehouseman's Problem [Int. J. ...
Tópico(s): Computational Geometry and Mesh Generation
2005 - Elsevier BV | Theoretical Computer Science
Carsten Lutz, Dirk Walther, Frank Wolter,
... common qualitative TLs are complete for NP or PSpace, their metric extensions are often ExpSpace-complete or ... of the real line that are at most PSpace-complete, and analyze the transition from NP to PSpace for such logics. Our first result is that ... time units in the past/future’ is still PSpace-complete. In contrast to existing results, we also ... assumption is not made. To establish containment in PSpace, we use a novel reduction technique that can ... coding of parameters is assumed: satisfiability is still PSpace-complete under binary coding, but only NP-complete ...
Tópico(s): Logic, programming, and type systems
2006 - Elsevier BV | Information and Computation
... every set A, ${\operatorname{PH}}(A) \ne {\operatorname{PSPACE}}(A)$. For every set A, there is a restricted relativization of the class ${\operatorname{PSPACE}}(A)$, denoted ${\operatorname{PQH}}(A)$, with the property ... A)$ lies between ${\operatorname{PH}}(A)$ and ${\operatorname{PSPACE}}(A)$ (as was previously studied in [Theoret. Comput. ... is shown here that ${\operatorname{PH}} \ne {\operatorname{PSPACE}}$ if and only if, for almost every set ... every set A, ${\operatorname{PQH}}(A) \ne {\operatorname{PSPACE}}(A)$, so that for almost every set A, ${\ ...
Tópico(s): Optimization and Search Problems
1991 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Robert A. Hearn, Erik D. Demaine,
... of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. ... to show that multiple motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to ... result that the restricted Rush Hour™ puzzles are PSPACE-complete [2], of which we also give a ... result that the pushing-blocks puzzle Sokoban is PSPACE-complete [1], by showing that it is PSPACE-complete even if no barriers are allowed.
Tópico(s): Algorithms and Data Compression
2002 - Springer Science+Business Media | Lecture notes in computer science
... weak periodic detectability of deterministic DESs are both PSPACE-hard (hence PSPACE-complete). Then as corollaries, the problems of determining ... weak periodic detectability of nondeterministic DESs are also PSPACE-hard (hence PSPACE-complete).
Tópico(s): Distributed systems and fault tolerance
2017 - Elsevier BV | Automatica
Rahul Singh, Hui Yang, Ben Dalziel, Daniel Asarnow, William Murad, David Foote, Matthew Gormley, Jonathon H. Stillman, Susan J. Fisher,
... time-series transcriptional data. The second system, called PSPACE (P rotein Spac e E xplorer) is designed ... reaction of marine organisms to heat stress. With PSPACE, we demonstrate how complex structure-function relationships can ... against comparable systems indicate that both XMAS and PSPACE deliver results with better interpretability while placing lower ... available at: http://tintin.sfsu.edu:8080/xmas . PSPACE is available at: http://pspace.info/ .
Tópico(s): Cell Image Analysis Techniques
2013 - BioMed Central | BMC Bioinformatics
Marco Gaboardi, Jean-Yves Marion, Simona Ronchi Della Rocca,
... conditional construction, named STA B , that characterizes the PSPACE class. This system is obtained by extending STA, ... Turing Machines. From the well-known result APTIME = PSPACE, it follows that STA B is complete for PSPACE. Conversely, inspired by the simulation of Alternating Turing ... we know, this is the first characterization of PSPACE that is based on lambda calculus and light ...
Tópico(s): Formal Methods in Verification
2012 - Association for Computing Machinery | ACM Transactions on Computational Logic
... computable in polynomial space by deterministic Turing machines – PSPACE. It gives an inductive characterization of PSPACE with no ad‐hoc initial functions and with ... of pointers (also called path information) to reach PSPACE. The presence of the pointers in the recursion ... is the main difference between this characterization of PSPACE and the well‐known Bellantoni‐Cook characterization of ...
Tópico(s): Cellular Automata and Applications
2008 - Wiley | Mathematical logic quarterly
Franz Baader, Jan Hladík, Rafael Peñaloza,
... worst-case optimal algorithms in the case of PSpace-complete logics, it is often very hard to ... usually also yield an ExpTime-algorithm for a PSpace-complete logic since the (tree) automaton constructed for ... large automaton can be used to obtain a PSpace-algorithm. We illustrate the usefulness of this approach by proving a new PSpace upper-bound for satisfiability of concepts with respect ...
Tópico(s): Natural Language Processing Techniques
2008 - Elsevier BV | Information and Computation
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger,
... and ${{R_{\rm Kt}}}$ are complete for ${{\rm{PSPACE}}}$ and {\mbox{\rm EXP}}, respectively, under ${\mbox{\rm ... Similar results hold for other classes with ${{\rm{PSPACE}}}$-robust Turing complete sets. \item ${\mbox{\rm EXP}} = {\mbox{\rm NP}}^{{{R_{\rm Kt}}}}.$ \item ${{\rm{PSPACE}}} = {\mbox{\rm ZPP}}^{{{R_{\rm KS}}}} \subseteq {\mbox{\ ... KT}}}}$. \end{remunerate} Our hardness result for ${{\rm{PSPACE}}}$ gives rise to fairly natural problems that are complete for ${{\rm{PSPACE}}}$ under ${\mbox{$\leq^{\rm p}_{\rm T}$}}$ reductions, ...
Tópico(s): Algorithms and Data Compression
2006 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Serge Abiteboul, Gerd G. Hillebrand,
... depth at most 2 can be evaluated in PSPACE, and this set of expressions is sufficient to ... syntactic condition on types) can be evaluated in PSPACE, and this set of terms expresses exactly the PSPACE queries; (3) There exists a set of second- ... simple syntactic characterization) that can be evaluated in PSPACE, and this set of schemas is sufficient to express all PSPACE queries.
Tópico(s): Semantic Web and Ontologies
1995 - Springer Science+Business Media | Lecture notes in computer science
José L. Balcázar, Ronald V. Book, Uwe Schöning,
... for each of the following results: (a) P = Pspace if and only if, for every set A, ... Pquery(A) (Selman et al., 1983): (b) NP = Pspace if and only if, for every set A, NP(A) = NPquery(S) (Book, 1981); (c) PH = Pspace if and only if, for every set A, ... PQH(A) (Book and Wrathall, 1981); (c) PH = Pspace if and only if, for every set set S, PH(S) = PQH(S) = Pspace(S) (Balcázar et al., 1986; Long and Selman, ...
Tópico(s): Advanced Graph Theory Research
1985 - Elsevier BV | Theoretical Computer Science
... NP}}$, we analyze the implications of NP and PSPACE having sparse, hard or complete sets for reduction ... are considered. First we show that if NP (PSPACE) has a tally $ \leqq _{k - T}^P $-hard ... then ${\text{P}} = {\text{NP}}$$({\text{P}} = {\text{PSPACE}})$. Here $ \leqq _{k - T}^P $ denotes a subcase ... oracle. We also show that if co-NP (PSPACE) has a sparse hard set for conjunctive polynomial ... then ${\text{P}} = {\text{NP}}$$({\text{P}} = {\text{PSPACE}})$.
Tópico(s): Computability, Logic, AI Algorithms
1983 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora,
... result is to show that this problem is PSPACE-complete on split graphs (and hence also on ... reduction shows that this more general problem is PSPACE-complete for all fixed c ≥ 1 on chordal ... except c = 1, for which the problem is PSPACE-complete. We complement our algorithm with a lower ... show that the problem on chordal graphs is PSPACE-complete even if c is some fixed constant. ...
Tópico(s): Nanocluster Synthesis and Applications
2020 - Springer Science+Business Media | Theory of Computing Systems
Produção Nacional
Revisado por pares
André G. Pereira, Marcus Ritt, Luciana S. Buriol,
We prove PSPACE-completeness of a broad class of moving-blocks problems similar to the well-known puzzle Sokoban. Several computational ... known NP-hardness results of Pull problems to PSPACE-completeness results. We also were able to show that the whole class of PushPull problems is PSPACE-complete.
Tópico(s): Logic, programming, and type systems
2016 - Elsevier BV | Theoretical Computer Science
... subsumes satisfiability of word equations, which is in PSPACE. We show that context unification is in PSPACE, so as word equations. For both problems NP ... and used in particular to obtain a new PSPACE algorithm for satisfiability of word equations, to context ...
Tópico(s): Semantic Web and Ontologies
2014 - Springer Science+Business Media | Lecture notes in computer science
Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani,
... Harsanyi-Selten equilibrium selection process for games, are PSPACE-complete to implement. Extending our result for the ... algorithms for finding equilibria of games are also PSPACE-complete to implement. A further application of our techniques yields the result that it is PSPACE-complete to compute any of the equilibria that ... can be widely applied and suggest that the PSPACE-completeness of implementing homotopy methods is a general ...
Tópico(s): Economic theories and models
2013 - Association for Computing Machinery | ACM Transactions on Economics and Computation
Stanislav Böhm, Stefan Göller, Petr Jančar,
... one-counter automata. The first main result shows PSPACE -completeness of bisimulation equivalence; this closes the complexity gap between decidability [23] and PSPACE -hardness [25] . The second main result shows NL - ... time one-counter automata; this improves the known PSPACE upper bound (indirectly shown by Valiant and Paterson [ ... one-counter automaton is regular. • Bisimulation equivalence is PSPACE -complete for real-time one-counter automata. • Language ...
Tópico(s): Software Testing and Debugging Techniques
2013 - Elsevier BV | Journal of Computer and System Sciences
Dror Fried, Solomon Eyal Shimony, Amit Benbassat, Cenny Wenner,
... version of the CTP was shown to be PSPACE-complete, with the stochastic version shown to be in PSPACE and #P-hard. We show that the stochastic CTP is also PSPACE-complete: initially proving PSPACE-hardness for the dependent version of the stochastic ...
Tópico(s): Complexity and Algorithms in Graphs
2013 - Elsevier BV | Theoretical Computer Science
... known to exist somewhere between NC^1 and PSPACE. We resolve this discrepancy by showing that deciding ... winner of an arbitrary finite poset game is PSPACE-complete. To this end, we give an explicit reduction from Node Kayles, a PSPACE-complete game in which players vie to chose ...
Tópico(s): Educational Games and Gamification
2013 - Springer Science+Business Media | Lecture notes in computer science
Eric Allender, Luke Friedman, William Gasarch,
... has shown: • BPP ⊆ { A : A ⩽ tt p R } . • PSPACE ⊆ P R . • NEXP ⊆ NP R . Since these inclusions ... of how “ R ” is defined, and since BPP , PSPACE and NEXP are all in Δ 1 0 ( ... U { A : A ⩽ tt p R K U } ⊆ PSPACE . • NEXP ⊆ Δ 1 0 ∩ ⋂ U NP R K U ⊆ EXPSPACE . Hence, in particular, PSPACE is sandwiched between the class of sets polynomial- ...
Tópico(s): semigroups and automata theory
2012 - Elsevier BV | Information and Computation
... logics. We show that PML satisfiability is only pspace-complete by designing a Ladner-like algorithm that ... This extends a well-known and non-trivial pspace upper bound for graded modal logic. Furthermore, we ... show that satisfiability for Sheaves Logic SL is pspace-complete, improving significantly its best known upper bound.
Tópico(s): Semantic Web and Ontologies
2006 - Springer Science+Business Media | Lecture notes in computer science
Kurt Rohloff, Stéphane Lafortune,
... related to the supervision of these systems are PSPACE-complete. This shows that although there may be ... modular system to achieve a global specification is PSPACE-complete. We also show many verification problems for system supervision are PSPACE-complete, even for prefix-closed cases. Supervisor admissibility ...
Tópico(s): Distributed systems and fault tolerance
2005 - Springer Science+Business Media | Discrete Event Dynamic Systems
Jeffrey R. Hartline, Ran Libeskind-Hadas,
... In particular, we show that the problem is PSPACE-complete. We begin with a review of NP-completeness and polynomial-time reductions, introduce the class PSPACE, and motivate the significance of PSPACE-complete problems. Afterwards, we prove that determining whether ... a generalized Lunar Lockout puzzle is solvable is PSPACE-complete.
Tópico(s): AI-based Problem Solving and Planning
2003 - Society for Industrial and Applied Mathematics | SIAM Review
... bisimulation problems for pushdown automata are at least PSPACE-hard. In particular, we show that (1) Weak bisimilarity of pushdown automata and finite automata is PSPACE-hard, even for a small fixed finite automaton, ( ... bisimilarity of pushdown automata and finite automata is PSPACE-hard, but polynomial for every fixed finite automaton, ( ... w.r.t. weak and strong bisimilarity is PSPACE-hard.
Tópico(s): Organoboron and organosilicon chemistry
2000 - Springer Science+Business Media | Lecture notes in computer science
Jean-Camille Birget, Samuel Margolis, John Meakin, Pascal Weil,
... that testing for this property of H is PSPACE-complete. In the process, we show that certain problems about finite automata which are PSPACE-complete in general remain PSPACE-complete when restricted to injective and inverse automata ( ...
Tópico(s): Finite Group Theory Research
2000 - Elsevier BV | Theoretical Computer Science
Madhav Marathe, Harry B. Hunt, Richard E. Stearns, Venkatesh Babu Radhakrishnan,
... are the first polynomial time approximation schemes for PSPACE-hard hierarchically or periodically specified problems. Since several of the problems considered are PSPACE-hard, our results provide the first examples of natural PSPACE-hard optimization problems that have polynomial time approximation ...
Tópico(s): Formal Methods in Verification
1998 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Anne Condon, Joan Feigenbaum, Carsten Lund, Peter W. Shor,
... debate if and only if L is in PSPACE [A. Condon, J. Feigenbaum, C. Lund, and P. ... debate if and only if L is in PSPACE. This new characterization of PSPACE is used to show that certain stochastic PSPACE-hard functions are as hard to approximate closely ...
Tópico(s): Bayesian Modeling and Causal Inference
1997 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing