Search results for "Pspace"

Hits ?▲	Authors	Title	Venue	Year	Link
18	Lear Bahack	The Game of Tumbleweed is PSPACE-complete.	CoRR	2022	DBLP DOI BibTeX RDF
18	Juan Pablo Aguilera Ozuna, Martín Diéguez, David Fernández-Duque, Brett McLean	Time and Gödel: Fuzzy temporal reasoning in PSPACE.	CoRR	2022	DBLP DOI BibTeX RDF
18	Yulong Li	A Simple Proof of PreciseQMA = PSPACE.	CoRR	2022	DBLP DOI BibTeX RDF
18	Valerii Sopin	PH = PSPACE.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
18	Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß	Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems.	ACM Trans. Comput. Theory	2022	DBLP DOI BibTeX RDF
18	Juan P. Aguilera 0001, Martín Diéguez, David Fernández-Duque, Brett McLean	Time and Gödel: Fuzzy Temporal Reasoning in PSPACE.	WoLLIC	2022	DBLP DOI BibTeX RDF
18	Erik D. Demaine, Robert A. Hearn, Dylan H. Hendrickson, Jayson Lynch	PSPACE-Completeness of Reversible Deterministic Systems.	MCU	2022	DBLP DOI BibTeX RDF
18	Austin Luchsinger	Brief Announcement: Barrier-1 Reachability for Thermodynamic Binding Networks Is PSPACE-Complete.	SAND	2022	DBLP DOI BibTeX RDF
18	Shankaranarayanan Krishna, Adwait Godbole, Roland Meyer 0001, Soham Chakraborty 0001	Parameterized Verification under Release Acquire is PSPACE-complete.	PODC	2022	DBLP DOI BibTeX RDF
18	Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch	Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude.	FUN	2022	DBLP DOI BibTeX RDF
18	Ayal Green, Guy Kindler, Yupan Liu	Towards a quantum-inspired proof for IP = PSPACE.	Quantum Inf. Comput.	2021	DBLP DOI BibTeX RDF
18	Bosheng Song, Xiangxiang Zeng	Solving a PSPACE-complete problem by symport/antiport P systems with promoters and membrane division.	J. Membr. Comput.	2021	DBLP DOI BibTeX RDF
18		Separation of PSPACE and EXP.	CoRR	2021	DBLP BibTeX RDF
18	Murray Elder, Adam Piggott	Detecting plainness in PSPACE.	CoRR	2021	DBLP BibTeX RDF
18	Tianrong Lin	The Separation of NP and PSPACE.	CoRR	2021	DBLP BibTeX RDF
18	Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken	Dots & Boxes is PSPACE-complete.	CoRR	2021	DBLP BibTeX RDF
18	Erik D. Demaine, Yevhenii Diomidov	Strings-and-Coins and Nimstring are PSPACE-complete.	CoRR	2021	DBLP BibTeX RDF
18	David Caballero, Timothy Gomez, Robert T. Schweller, Tim Wylie	Covert Computation in Staged Self-Assembly: Verification Is PSPACE-Complete.	ESA	2021	DBLP DOI BibTeX RDF
18	Satyadev Nandakumar, Subin Pulari	Ergodic Theorems and Converses for PSPACE Functions.	MFCS	2021	DBLP DOI BibTeX RDF
18	Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken	Dots & Boxes Is PSPACE-Complete.	MFCS	2021	DBLP DOI BibTeX RDF
18	Md Lutfar Rahman, Thomas Watson 0001	6-Uniform Maker-Breaker Game Is PSPACE-Complete.	STACS	2021	DBLP DOI BibTeX RDF
18	Laura Bozzelli, Angelo Montanari, Adriano Peron, Pietro Sala	Pspace-Completeness of the Temporal Logic of Sub-Intervals and Suffixes.	TIME	2021	DBLP DOI BibTeX RDF
18	Josh Brunner, Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff	1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete.	FUN	2021	DBLP DOI BibTeX RDF
18	Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch	Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets.	FUN	2021	DBLP DOI BibTeX RDF
18	Thomas Brocken, G. Wessel van der Heijden, Irina Kostitsyna, Lloyd E. Lo-Wong, Remco J. A. Surtel	Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard.	FUN	2021	DBLP DOI BibTeX RDF
18	Parosh Aziz Abdulla, Mohamed Faouzi Atig, Rojin Rezvan	Parameterized verification under TSO is PSPACE-complete.	Proc. ACM Program. Lang.	2020	DBLP DOI BibTeX RDF
18	Joshua Ani, Sualeh Asif, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch, Sarah Scheffler, Adam Suhl	PSPACE-completeness of Pulling Blocks to Reach a Goal.	J. Inf. Process.	2020	DBLP DOI BibTeX RDF
18	Eurinardo Rodrigues Costa, Victor Lage Pessoa, Rudini M. Sampaio, Ronan Soares	PSPACE-completeness of two graph coloring games.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
18	Md Lutfar Rahman, Thomas Watson 0001	6-Uniform Maker-Breaker Game Is PSPACE-Complete.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
18	Alec Henderson, Radu Nicolescu, Michael J. Dinneen	Solving a PSPACE-complete problem with cP systems.	J. Membr. Comput.	2020	DBLP DOI BibTeX RDF
18	Joshua Ani, Sualeh Asif, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch, Sarah Scheffler, Adam Suhl	PSPACE-completeness of Pulling Blocks to Reach a Goal.	CoRR	2020	DBLP BibTeX RDF
18	Josh Brunner, Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff	1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete.	CoRR	2020	DBLP BibTeX RDF
18	Satyadev Nandakumar, Subin Pulari	An Ergodic Theorem for PSPACE functions.	CoRR	2020	DBLP BibTeX RDF
18	John Fearnley, Rasmus Ibsen-Jensen, Rahul Savani	One-Clock Priced Timed Games are PSPACE-hard.	CoRR	2020	DBLP BibTeX RDF
18	Vidya Sagar Sharma, Piyush Srivastava 0001	The PSPACE-hardness of understanding neural circuits.	CoRR	2020	DBLP BibTeX RDF
18	Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan H. Hendrickson, Jayson Lynch	Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets.	CoRR	2020	DBLP BibTeX RDF
18	Lew Gordeev, Edward Hermann Haeusler	Proof Compression and NP Versus PSPACE II: Addendum.	CoRR	2020	DBLP BibTeX RDF
18	Thomas Brocken, G. Wessel van der Heijden, Irina Kostitsyna, Lloyd E. Lo-Wong, Remco J. A. Surtel	Multi-robot motion planning of k-colored discs is PSPACE-hard.	CoRR	2020	DBLP BibTeX RDF
18	Guanjun Liu	PSPACE-Completeness of the Soundness Problem of Safe Asymmetric-Choice Workflow Nets.	Petri Nets	2020	DBLP DOI BibTeX RDF
18	John Fearnley, Rasmus Ibsen-Jensen, Rahul Savani	One-Clock Priced Timed Games are PSPACE-hard.	LICS	2020	DBLP DOI BibTeX RDF
18	William Vega-Brown, Nicholas Roy	Task and Motion Planning Is PSPACE-Complete.	AAAI	2020	DBLP DOI BibTeX RDF
18	Dmitry Chistikov 0001, Grzegorz Lisowski, Mike Paterson, Paolo Turrini	Convergence of Opinion Diffusion is PSPACE-Complete.	AAAI	2020	DBLP DOI BibTeX RDF
18	Jan Philipp Wächter, Armin Weiß	An Automaton Group with PSPACE-Complete Word Problem.	STACS	2020	DBLP DOI BibTeX RDF
18	David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert T. Schweller, Tim Wylie	Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete.	CCCG	2020	DBLP BibTeX RDF
18	Dhiraj Holden, Yael Tauman Kalai	Non-signaling proofs with o(√ log n) provers are in PSPACE.	STOC	2020	DBLP DOI BibTeX RDF
18	Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß	Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems.	CCC	2020	DBLP DOI BibTeX RDF
18	Eurinardo Rodrigues Costa, Victor Lage Pessoa, Rudini Menezes Sampaio, Ronan Soares	PSPACE-hardness of Two Graph Coloring Games.	LAGOS	2019	DBLP DOI BibTeX RDF
18	Zeyu Guo 0001, Nitin Saxena 0001, Amit Sinhababu	Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field.	Theory Comput.	2019	DBLP DOI BibTeX RDF
18	Wojciech Plandowski	On PSPACE generation of a solution set of a word equation and its applications.	Theor. Comput. Sci.	2019	DBLP DOI BibTeX RDF
18	Lev Gordeev, Edward Hermann Haeusler	Proof Compression and NP Versus PSPACE.	Stud Logica	2019	DBLP DOI BibTeX RDF
18	Viliam Geffert	Unary Coded PSPACE-Complete Languages in ASPACE(loglog n).	Theory Comput. Syst.	2019	DBLP DOI BibTeX RDF
18	Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron	Characterizing PSPACE with shallow non-confluent P systems.	J. Membr. Comput.	2019	DBLP DOI BibTeX RDF
18	Ayal Green, Yupan Liu, Guy Kindler	Towards a quantum-inspired proof for IP = PSPACE.	CoRR	2019	DBLP BibTeX RDF
18	Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß	Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems.	CoRR	2019	DBLP BibTeX RDF
18	Jan Philipp Wächter, Armin Weiß	An Automaton Group with PSPACE-Complete Word Problem.	CoRR	2019	DBLP BibTeX RDF
18	Laura Ciobanu, Murray Elder	Solutions sets to systems of equations in hyperbolic groups are EDT0L in PSPACE.	CoRR	2019	DBLP BibTeX RDF
18	Lev Gordeev	Proof compression and NP versus PSPACE. Part 2.	CoRR	2019	DBLP BibTeX RDF
18	Dmitry Chistikov 0001, Grzegorz Lisowski, Mike Paterson, Paolo Turrini	Convergence of Opinion Diffusion is PSPACE-complete.	CoRR	2019	DBLP BibTeX RDF
18	Dhiraj Holden, Yael Kalai	No-Signaling Proofs with O(√(log n)) Provers are in PSPACE.	CoRR	2019	DBLP BibTeX RDF
18	Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron	Characterizing PSPACE with shallow non-confluent P systems.	CoRR	2019	DBLP BibTeX RDF
18	Jia Tao 0001	A PSpace Algorithm for Acyclic Epistemic DL ALCS5m.	J. Autom. Reason.	2019	DBLP DOI BibTeX RDF
18	Kyle Burke, Robert A. Hearn	PSPACE-complete two-color planar placement games.	Int. J. Game Theory	2019	DBLP DOI BibTeX RDF
18	Lijie Chen 0001, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein	Fine-grained Complexity Meets IP = PSPACE.	SODA	2019	DBLP DOI BibTeX RDF
18	Laura Ciobanu, Murray Elder	Solutions Sets to Systems of Equations in Hyperbolic Groups Are EDT0L in PSPACE.	ICALP	2019	DBLP DOI BibTeX RDF
18	Christoforos Keroglou, Christoforos N. Hadjicostis	Verification of AA-Diagnosability in Probabilistic Finite Automata is PSPACE-Hard.	CDC	2019	DBLP DOI BibTeX RDF
18	Christoph Scholl 0001, Jie-Hong Roland Jiang, Ralf Wimmer 0001, Aile Ge-Ernst	A PSPACE Subclass of Dependency Quantified Boolean Formulas and Its Effective Solving.	AAAI	2019	DBLP DOI BibTeX RDF
18	Rémi Nollet, Alexis Saurin, Christine Tasson	PSPACE-Completeness of a Thread Criterion for Circular Proofs in Linear Logic with Least and Greatest Fixed Points.	TABLEAUX	2019	DBLP DOI BibTeX RDF
18	Jan Hazla, Ali Jadbabaie, Elchanan Mossel, M. Amin Rahimian	Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard.	COLT	2019	DBLP BibTeX RDF
18	Zeyu Guo 0001, Nitin Saxena 0001, Amit Sinhababu	Algebraic dependencies and PSPACE algorithms in approximative complexity.	Electron. Colloquium Comput. Complex.	2018	DBLP BibTeX RDF
18	Martin Böhm 0001, Pavel Veselý 0001	Online Chromatic Number is PSPACE-Complete.	Theory Comput. Syst.	2018	DBLP DOI BibTeX RDF
18	Zeyu Guo 0001, Nitin Saxena 0001, Amit Sinhababu	Algebraic dependencies and PSPACE algorithms in approximative complexity.	CoRR	2018	DBLP BibTeX RDF
18	Parosh Aziz Abdulla, Mohamed Faouzi Atig, Radu Ciobanu, Richard Mayr, Patrick Totzke	Universal Safety for Timed Petri Nets is PSPACE-complete.	CoRR	2018	DBLP BibTeX RDF
18	Lijie Chen 0001, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein	Fine-grained Complexity Meets IP = PSPACE.	CoRR	2018	DBLP BibTeX RDF
18	Sougata Bose, Anca Muscholl, Vincent Penelle, Gabriele Puppis	Origin-equivalence of two-way word transducers is in PSPACE.	CoRR	2018	DBLP BibTeX RDF
18	Jan Hazla, Ali Jadbabaie, Elchanan Mossel, M. Amin Rahimian	Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard.	CoRR	2018	DBLP BibTeX RDF
18	Géraud Sénizergues, Armin Weiß	The isomorphism problem for finite extensions of free groups is in PSPACE.	CoRR	2018	DBLP BibTeX RDF
18	Géraud Sénizergues, Armin Weiß	The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE.	ICALP	2018	DBLP DOI BibTeX RDF
18	Demen Güler, Andreas Krebs, Klaus-Jörn Lange, Petra Wolf 0002	Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy.	LATA	2018	DBLP DOI BibTeX RDF
18	Davide Tateo, Jacopo Banfi, Alessandro Riva, Francesco Amigoni, Andrea Bonarini	Multiagent Connected Path Planning: PSPACE-Completeness and How to Deal With It.	AAAI	2018	DBLP DOI BibTeX RDF
18	Jonathan Gabor, Aaron Williams	Switches are PSPACE-Complete.	CCCG	2018	DBLP BibTeX RDF
18	Parosh Aziz Abdulla, Mohamed Faouzi Atig, Radu Ciobanu, Richard Mayr, Patrick Totzke	Universal Safety for Timed Petri Nets is PSPACE-complete.	CONCUR	2018	DBLP DOI BibTeX RDF
18	Jean-Marie Lagniez, Daniel Le Berre, Tiago de Lima, Valentin Montmirail	A SAT-Based Approach For PSPACE Modal Logics.	KR	2018	DBLP BibTeX RDF
18	Michael A. Forbes 0001, Amir Shpilka	A PSPACE construction of a hitting set for the closure of small algebraic circuits.	STOC	2018	DBLP DOI BibTeX RDF
18	Davide Bilò, Luciano Gualà, Stefano Leucci 0001, Guido Proietti, Mirko Rossi	On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games.	FUN	2018	DBLP DOI BibTeX RDF
18	Tomás Masopust, Markus Krötzsch	Deciding Universality of ptNFAs is PSpace-Complete.	SOFSEM	2018	DBLP DOI BibTeX RDF
18	Sougata Bose, Anca Muscholl, Vincent Penelle, Gabriele Puppis	Origin-Equivalence of Two-Way Word Transducers Is in PSPACE.	FSTTCS	2018	DBLP DOI BibTeX RDF
18	Zeyu Guo 0001, Nitin Saxena 0001, Amit Sinhababu	Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity.	CCC	2018	DBLP DOI BibTeX RDF
18	Bostjan Bresar, Michael A. Henning	The game total domination problem is log-complete in PSPACE.	Inf. Process. Lett.	2017	DBLP DOI BibTeX RDF
18	Mukul Agarwal	PSPACE hardness of approximating the capacity of time-invariant Markov channels with perfect feedback.	Commun. Inf. Syst.	2017	DBLP DOI BibTeX RDF
18	Kuize Zhang	The problem of determining the weak (periodic) detectability of discrete event systems is PSPACE-complete.	Autom.	2017	DBLP DOI BibTeX RDF
18	Weihua He, Ziwen Liu, Chao Yang 0003	Snowman is PSPACE-complete.	Theor. Comput. Sci.	2017	DBLP DOI BibTeX RDF
18	Michael A. Forbes 0001, Amir Shpilka	A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits.	Electron. Colloquium Comput. Complex.	2017	DBLP BibTeX RDF
18	Mukul Agarwal, Sanjoy K. Mitter	Computing the capacity of a Markoff channel with perfect feedback is PSPACE-hard.	CoRR	2017	DBLP BibTeX RDF
18	Michael A. Forbes 0001, Amir Shpilka	A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits.	CoRR	2017	DBLP BibTeX RDF
18	Viliam Geffert	Unary Coded PSPACE-Complete Languages in ASPACE(loglog n).	CSR	2017	DBLP DOI BibTeX RDF
18	Reino Niskanen	Reachability Problem for Polynomial Iteration Is PSPACE-complete.	RP	2017	DBLP DOI BibTeX RDF
18	Paolo Marin, Massimo Narizzano, Luca Pulina, Armando Tacchella, Enrico Giunchiglia	Twelve Years of QBF Evaluations: QSAT Is PSPACE-Hard and It Shows.	Fundam. Informaticae	2016	DBLP DOI BibTeX RDF
18	Eric Goles 0001, Pedro Montealegre 0001, Ville Salo, Ilkka Törmä	PSPACE-completeness of majority automata networks.	Theor. Comput. Sci.	2016	DBLP DOI BibTeX RDF
18	Bernd Meyer 0008	Generalized Pete's Pike is PSPACE-complete.	Theor. Comput. Sci.	2016	DBLP DOI BibTeX RDF
18	André Grahl Pereira, Marcus Ritt, Luciana S. Buriol	Pull and PushPull are PSPACE-complete.	Theor. Comput. Sci.	2016	DBLP DOI BibTeX RDF