Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Graph isomorphism is low for PP (1992)
    Springer
    Computational complexity 2 (1992), S. 301-330 
    Details
    ISSN: 1420-8954
    Keywords: graph isomorphism ; complexity classes ; lowness ; counting properties ; 68Q15 ; 68Q25 ; 05C60 ; 68R10
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We show that the graph isomorphism problem, is low for PP and for C=P, i.e., it does not provide a PP or C=P computation with any additional power when used as an oracle. Furthermore, we show that graph isomorphism belongs to the class LWPP (see Fenner, Fortnow, Kurtz [12]). A similar result holds for the (apparently more difficult) problem Group Factorization. The problem of determining whether a given graph has a nontrivial automorphism, Graph Automorphism, is shown to be in SPP, and is therefore low for PP, C=P, and Mod k P,k≥2.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01200427
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Self-reducible sets of small density (1991)
    Springer
    Theory of computing systems 24 (1991), S. 83-100 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We study the complexity of sets that are at the same time self-reducible and sparse orm-reducible to sparse sets. We show that sets of this kind are low for the complexity classes Δ 2 p , Θ 2 p , NP, or P, depending on the type of self-reducibility used and on certain restrictions imposed on the query mechanism of the self-reducibility machines. The proof of some of these results is based on graph-theoretic properties that hold for the graphs induced by the self-reducibility structures.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02090392
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Classes of bounded nondeterminism (1990)
    Springer
    Theory of computing systems 23 (1990), S. 21-32 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We study certain language classes located betweenP andNP that are defined by polynomial-time machines with a bounded amount of nondeterminism. We observe that these classes have complete problems and find a characterization of the classes using robust machines with bounded access to the oracle, obtaining some other results in this direction. We also study questions related to the existence of complete tally sets in these classes and closure of the classes under different types of polynomial-time reducibilities.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02090764
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    On counting and approximation (1989)
    Springer
    Acta informatica 26 (1989), S. 363-379 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary We introduce a new class of functions, called span functions which count the different output values that occur at the leaves of the computation tree associated with a nondeterministic polynomial time Turing machine transducer. This function class has natural complete problems; it is placed between Valiant's function classes # P and # NP, and contains both Goldberg and Sipser's ranking functions for sets in NP, and Krentel's optimization functions. We show that it is unlikely that the span functions coincide with any of the mentioned function classes. A probabilistic approximation method (using an oracle in NP) is presented to approximate span functions up to any desired degree of accuracy. This approximation method is based on universal hashing and it never underestimates the correct value of the approximated function.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00276023
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...