Promise problems and access to unambiguous computation

DOI10.1007/3-540-55808-X_14MaRDI QIDQ5096827zbMATH OpenFDO

Authors Jin-Yi Cai, Lane A. Hemaspaandra, Jozef Vyskoč

Publication date 18 August 2022

Published in Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55808-X_14

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 512802
• Fundamentals of Computation Theory
• Hierarchical Unambiguity
• Hierarchical Unambiguity
• Unambiguous computations and locally definable acceptance types

Cites work

• A comparison of polynomial time reducibilities
• A complexity theory for feasible closure properties
• Bounded queries to SAT and the Boolean hierarchy
• Bounded Query Classes
• Complexity classes without machines: on complete languages for UP
• Complexity Measures for Public-Key Cryptosystems
• Computational Complexity of Probabilistic Turing Machines
• Cryptocomplexity and NP-completeness
• Graph isomorphism is low for PP
• On helping by robust oracle machines
• On some natural complete operators
• ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
• One-way functions and the nonisomorphism of NP-complete sets
• Polynomial Time Enumeration Reducibility
• Quantitative Relativizations of Complexity Classes
• Reductions on NP and p-selective sets
• Relative complexity of checking and evaluating
• Robust algorithms: a different approach to oracles
• Robust machines accept easy sets
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Strong nondeterministic polynomial-time reducibilities
• The complexity of promise problems with applications to public-key cryptography
• The strong exponential hierarchy collapses

Cited in

(6)

• Unambiguous computations and locally definable acceptance types
• On the probabilistic closure of the loose unambiguous hierarchy
• Hierarchical Unambiguity
• scientific article; zbMATH DE number 512802 (Why is no real title available?)
• Fault-tolerance and complexity (extended abstract)
• Fundamentals of Computation Theory

This page was built for publication: Promise problems and access to unambiguous computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096827)