Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > UNAMBIGUOUS COMPUTATIONS:
Reports tagged with unambiguous computations:
TR96-060 | 19th November 1996
Bernd Borchert, Frank Stephan

#### Looking for an Analogue of Rice's Theorem in Complexity Theory

Rice's Theorem says that every nontrivial semantic property
of programs is undecidable. It this spirit we show the following:
Every nontrivial absolute (gap, relative) counting property of circuits
is UP-hard with respect to polynomial-time Turing reductions.

more >>>

TR04-064 | 25th June 2004
Piotr Faliszewski

#### Exponential time reductions and sparse languages in NEXP

In this paper we define a many-one reduction which is allowed to work in exponential time but may only output polynomially many symbols. We show that there are no NEXP-hard sparse languages under our reduction unless EXP=UEXP.

more >>>

TR14-050 | 21st March 2014
Edward Hirsch, Dmitry Sokolov

#### On the probabilistic closure of the loose unambiguous hierarchy

Revisions: 1

Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy $prUH_\bullet$ with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that ... more >>>

TR18-088 | 24th April 2018
Ilya Volkovich

#### A story of AM and Unique-SAT

Revisions: 1

In the seminal work of \cite{Babai85}, Babai have introduced \emph{Arthur-Merlin Protocols} and in particular the complexity classes $MA$ and $AM$ as randomized extensions of the class $NP$. While it is easy to see that $NP \subseteq MA \subseteq AM$, it has been a long standing open question whether these classes ... more >>>

ISSN 1433-8092 | Imprint