MURAL - Maynooth University Research Archive Library



    Random nondeterministic real functions and Arthur Merlin games


    Moser, Philippe (2002) Random nondeterministic real functions and Arthur Merlin games. Technical Report. Electronic Colloquium on Computational Complexity.

    [img]
    Preview
    Download (227kB) | Preview
    Official URL: https://eccc.weizmann.ac.il/report/2002/006/


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    We construct a nondeterministic version of \textbf{APP}, denoted \textbf{NAPP}, which is the set of all real valued functions f:01[01] , that are approximable within 1/k, by a probabilistic nondeterministic transducer, in time poly(1kn ). We show that the subset of all Boolean functions in \mbfNAPP is exactly \textbf{AM}. We exhibit a natural complete problem for \textbf{NAPP}, namely computing the acceptance probability of a nondeterministic Boolean circuit. Then we prove that similarly to \textbf{AM}, the error probability for \textbf{NAPP} functions can be reduced exponentially. We also give a co-nondeterministic version, denoted \textbf{coNAPP}, and prove that all results for \textbf{NAPP} also hold for \textbf{coNAPP}. Then we construct two mappings between \tbf{NAPP} and promise-\tbf{AM}, which preserve completeness. Finally we show that in the world of deterministic computation, oracle access to \textbf{AM} is the same as oracle access to \textbf{NAPP}, i.e. \mbfP\mbfNAPP=\mbfP\mbfprAM.

    Item Type: Monograph (Technical Report)
    Keywords: Arthur Merlin games; Randomness; real functions;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 10309
    Identification Number: Revision #1 to TR02-006
    Depositing User: Philippe Moser
    Date Deposited: 11 Dec 2018 16:35
    Publisher: Electronic Colloquium on Computational Complexity
    URI:
      Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

      Repository Staff Only(login required)

      View Item Item control page

      Downloads

      Downloads per month over past year

      Origin of downloads