Cover Image

Limit-sure reachability for small memory policies in POMDPs is NP-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Asadi, Ali, Chatterjee, Krishnendu, Saona, Raimundo, Shafiee, Ali
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
by: Asadi, Ali, et al.
Published: (2025)

On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets
by: Asadi, Ali, et al.
Published: (2026)

Value Iteration with Guessing for Markov Chains and Markov Decision Processes
by: Chatterjee, Krishnendu, et al.
Published: (2025)

Linear Equations with Min and Max Operators: Computational Complexity
by: Chatterjee, Krishnendu, et al.
Published: (2024)

Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights
by: Asadi, Ali, et al.
Published: (2024)

Concurrent Stochastic Games with Stateful-discounted and Parity Objectives: Complexity and Algorithms
by: Asadi, Ali, et al.
Published: (2024)

Uniform Value and Decidability in Ergodic Blind Stochastic Games
by: Chatterjee, Krishnendu, et al.
Published: (2024)

Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs
by: Asadi, Ali, et al.
Published: (2026)

BusOut is NP-complete
by: Ishibashi, Takehiro, et al.
Published: (2025)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
by: Çivril, Ali
Published: (2021)

Scheme-theoretic Approach to Computational Complexity II. The Separation of P and NP over $\mathbb{C}$, $\mathbb{R}$, and $\mathbb{Z}$
by: Çivril, Ali
Published: (2021)

Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
by: Binnendyk, Eric
Published: (2025)

Limits of structures and Total NP Search Problems
by: Ježil, Ondřej
Published: (2023)

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
by: Pfaue, Femke
Published: (2024)

P=NP
by: Deng, Zikang
Published: (2024)

Wataridori is NP-Complete
by: Ruangwises, Suthee
Published: (2026)

P vs. NP
by: Uribe, Daniel
Published: (2016)

On P Versus NP
by: Gordeev, Lev
Published: (2020)

Nondango is NP-Complete
by: Ruangwises, Suthee
Published: (2023)

The n-vehicle exploration problem is NP-complete
by: Cui, Jinchuan, et al.
Published: (2023)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

Proofs of NP = coNP = PSPACE: Current upgrade
by: Gordeev, Lev, et al.
Published: (2023)

On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
by: DeJesse, Nicholas, et al.
Published: (2025)

Information Accessibility Limits in Structured NP Search
by: Wei, Jing-Yuan
Published: (2026)

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

On Kernelization with Access to NP-Oracles
by: Molter, Hendrik, et al.
Published: (2025)

NP-Completeness of Neighborhood Balanced Colorings
by: Asaeedi, Saeed
Published: (2024)

A Critique of Deng's "P=NP"
by: Humphreys, Isabel, et al.
Published: (2025)

The 2-Attractor Problem is NP-Complete
by: Fuchs, Janosch, et al.
Published: (2023)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
by: Yang, Chao, et al.
Published: (2024)

Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
by: Zhan, Junpeng
Published: (2023)

NP-Completeness of Multicast Beamforming in Wireless Communication
by: Shrestha, Sagar
Published: (2025)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)

Some conditions implying if P=NP then P=PSPACE
by: Rodriguez, Ismael
Published: (2026)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
by: Mitosek, Piotr
Published: (2024)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
by: Martinsson, Björn
Published: (2024)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
by: Romão, Leonardo Gasparini, et al.
Published: (2025)

The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
by: Meng, Boning, et al.
Published: (2025)

The 7 faces of quantum NP
by: Gharibian, Sevag
Published: (2023)