Promise problems and access to unambiguous computation
From MaRDI portal
Publication:5096827
DOI10.1007/3-540-55808-X_14zbMath1493.68157MaRDI QIDQ5096827
Jozef Vyskoč, Hemaspaandra, Lane A., Jin-Yi Cai
Publication date: 18 August 2022
Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
Unambiguous computations and locally definable acceptance types ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ On the probabilistic closure of the loose unambiguous hierarchy
Cites Work
- The strong exponential hierarchy collapses
- Robust machines accept easy sets
- Strong nondeterministic polynomial-time reducibilities
- Robust algorithms: a different approach to oracles
- On some natural complete operators
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- On helping by robust oracle machines
- Complexity classes without machines: on complete languages for UP
- Reductions on NP and p-selective sets
- Bounded queries to SAT and the Boolean hierarchy
- Graph isomorphism is low for PP
- A comparison of polynomial time reducibilities
- Relative complexity of checking and evaluating
- A complexity theory for feasible closure properties
- One-way functions and the nonisomorphism of NP-complete sets
- Bounded Query Classes
- The complexity of promise problems with applications to public-key cryptography
- Quantitative Relativizations of Complexity Classes
- Complexity Measures for Public-Key Cryptosystems
- Cryptocomplexity and NP-completeness
- ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
- Computational Complexity of Probabilistic Turing Machines
- Polynomial Time Enumeration Reducibility
This page was built for publication: Promise problems and access to unambiguous computation
