Many bounded versions of undecidable problems are \textsf{NP}-hard
From MaRDI portal
Publication:6594491
Cites work
- A variant of a recursively unsolvable problem
- Classical deterministic complexity of Edmonds' Problem and quantum entanglement
- Computational Complexity
- Decidable and Undecidable Problems about Quantum Automata
- Fundamental limitations in the purifications of tensor networks
- Halos and undecidability of tensor stable positive maps
- scientific article; zbMATH DE number 5595162 (Why is no real title available?)
- scientific article; zbMATH DE number 3592969 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3336816 (Why is no real title available?)
- Mathematics and computation. A theory revolutionizing technology and science
- MIP* = RE
- Mortality in Matrix Semigroups
- Nonlocal games, compression theorems, and the arithmetical hierarchy
- On the Computational Complexity of Program Scheme Equivalence
- Positivity of linear maps under tensor powers
- Quantum logic is undecidable
- Strong NP-hardness of the quantum separability problem
- The Complexity of the Local Hamiltonian Problem
- The set of quantum correlations is not closed
- The undecidability of the domino problem
- Translationally invariant universal classical Hamiltonians
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Unsolvability in 3 × 3 Matrices
- When is a pair of matrices mortal?
Cited in
(2)
This page was built for publication: Many bounded versions of undecidable problems are \textsf{NP}-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6594491)
