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
    Complete sets and closeness to complexity classes (1986)
    Springer
    Theory of computing systems 19 (1986), S. 29-41 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider two setsA andB to be close to each other if the census of their symmetric difference,A ▵B, is a slowly increasing function (e.g. a polynomial.) The classes of sets which are polynomially close to some set in a complexity classC (likeP) are studied and characterized. We investigate the question whether complete sets forNP or EXPTIME can be polynomially close to a set inP. Some of the obtained results strengthen or generalize results by Yesha [24], e.g. it is shown that no EXPTIME-hard set can be polynomially close to any set inP.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01704904
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Bi-immune sets for complexity classes (1985)
    Springer
    Theory of computing systems 18 (1985), S. 1-10 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract An infinite and co-infinite setA is bi-immune for a complexity classC if neitherA nor its complement has an infinite subset inC. We prove various equivalent characterizations of this notion. Also, we introduce a stronger version of bi-immunity and show how both notions relate to density and other properties of sets in EXPTIME.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01699457
    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
  • 5
    Book
    Book
    Logic for computer scientists; 8 (1989)
    Basel u.a. :Birkhäuser,
    Details
    Title: Logic for computer scientists; 8
    Author: Schöning, Uwe
    Publisher: Basel u.a. :Birkhäuser,
    Year of publication: 1989
    Pages: 166 S.
    Series Statement: Progress in computer science and applied logic 8
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 6
    Book
    Book
    Gems of theoretical computer science : Perlen der theoretischen Informatik, engl. (1998)
    Berlin u.a. :Springer,
    Details
    Title: Gems of theoretical computer science : Perlen der theoretischen Informatik, engl.
    Author: Schöning, Uwe
    Contributer: Pruim, Randall
    Publisher: Berlin u.a. :Springer,
    Year of publication: 1998
    Pages: 320 S.
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 7
    Book
    Book
    Algorithmik (2001)
    Heidelberg :Spektrum Akademischer Verl.,
    Details
    Title: Algorithmik
    Author: Schöning, Uwe
    Publisher: Heidelberg :Spektrum Akademischer Verl.,
    Year of publication: 2001
    Pages: 384 S.
    Series Statement: Spektrum Lehrbuch
    ISBN: 3-8274-1092-4
    Type of Medium: Book
    Language: German
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...